Syllabus

Here is the complete syllabus. --Click here.--

Long Distance Students

I will be using Zoom to stream and record lectures. You will need to use a web-camera. The same link is also for office hours. Here is the zoom information:

Thomas Schwarz is inviting you to a scheduled Zoom meeting.

Topic: Algorithms
Time: This is a recurring meeting Meet anytime

Join Zoom Meeting
https://us02web.zoom.us/j/81258461828?pwd=WElTYlJxRU8ybkhONyt6ZXlFOEZhUT09

Meeting ID: 812 5846 1828
Passcode: 834069

Office Hours

• MWF 14:30 - 15:20.
• by appointment

Examinations

• --> Final (click here) <--

Contents

Week 1

Class 1: Introduction

August 29, 2022

Introduction

• Presentation (pdf) [click here]
• Presentation (key) [click here]
• Recording (mp4) A29.mp4

Class 2: Correctness and Loop Invariants

August 31, 2022

Introduction

• Presentation (pdf) [click here]
• Presentation (key) [click here]
• Recording (mp4) A31.mp4

Week 2

Class 3: Divide and Conquer, Recurrence Relations

September 5, 2022

• Divide and Conquer (pdf) [click here]
• Divide and Conquer (key) [click here]
• Recurrence (pdf) [click here]
• Recurrence (key) [click here]
• Recording (mp4) S7.mp4

Homework 1

Submit only in pdf. If your solution is hand written, make sure it is legible (e.g. high contrast between ink and paper) and import it into a document with the right orientation before creating a pdf version.

Due September 14, 2022

• Homework 1 hw1.pdf
• Python Code for Problem 3 hw1code.py

Week 3

Class 4: Dictionaries: B-Trees

September 12, 2022

• Data Structures (pdf) [click here]
• Data Structures (key) [click here]
• Recording (mp4) S12.mp4

Class 5: Containers: Linear Hashing

September 14, 2022

• Data Structures (pdf) [click here]
• Data Structures (key) [click here]
• Recording (mp4) September14.mp4

Homework 2

Due Spetember 21, 2022

• Homework 2 hw2.pdf

Week 4

Class 6: Multiprocessor Programming 1

September 19, 2022

• Parallel Programming 1 (pdf) [click here]
• Parallel Programming 1 (key) [click here]
• Recording (mp4) September19.mp4

Class 7: Multiprocessor Programming 2

September 21, 2022

• Parallel Programming 2 (pdf) [click here]
• Parallel Programming 2 (key) [click here]
• Recording (mp4) September21.mp4

Due September 28, 2022

• Homework 3 hw3.pdf

Class 8: Locking Algorithms

September 26, 2022

• Parallel Programming 2 (pdf) [click here]
• Consensus (pdf) [click here]
• Recording (mp4) September21.mp4

Class 9: Consensus

September 28, 2022

• Consensus (pdf) [click here]
• Consensus (key) [click here]
• Recording (mp4) September21.mp4

Due October 5, 2022

• Homework 4 hw4.pdf

Class 10: Spin Locks with hardware support

October 3, 2022

• Consensus (pdf) [click here]
• Consensus (key) [click here]
• Recording (mp4) September21.mp4

Class 11: Thread Safe Linked lists

October 5, 2022

• Linked List (pdf) [click here]
• keynote [click here]
• Recording (mp4) September21.mp4

Due October 12, 2022

• Homework 5 hw4.pdf

Class 12: Optimistic linked lists; Lazy optimistic linked lists and CAS

October 10, 2022

• Linked List (pdf) [click here]
• keynote [click here]
• Recording (mp4) October10.mp4

Class 13: Memory Hierarchy, Disks, Flash Memory Architecture

October 12, 2022

• Storage (pdf) [click here]
• Recording (mp4) October12.mp4

Class 14: Concurrency for B-Trees

October 17, 2022

• Concurrency for B-trees [click here]
• Srinivasan, Carey: Performance of B-Tree Concurrency Control Algorithms Paper at ACM DL
• Recording (mp4) October17.mp4

Class 15: Data Structures for NVRAM and PCM in particular

October 19, 2022

• Class given by David Roy, SJ

Class 16: Amortized Analysis

October 22, 2022

• Presentation (pdf) [click here]
• Recording (mp4) October22.mp4

Class 17: Adorning Data Structures: Binary trees and priority queues

October 24, 2022

• Presentation(pdf) [click here]
• Recording (mp4) October24.mp4

Class 18: Fibonacci Heaps

October 31, 2022

• Presentation (pdf) [click here]
• Recording (mp4) October29.mp4

Class 19: Bloom Filters & Fibonacci Heaps

October 31, 2022

• Presentation (pdf) [click here]
• Presentation (pdf) [click here]
• Recording (mp4) Oct31.mp4
• Reading [click here]

Class 20: Set Structures

November 2, 2022

• Presentation (pdf) [click here]
• Recording (mp4) Nov2.mp4

Class 21: Set Structures

November 7, 2022

• Presentation (pdf) [click here]
• Recording (mp4) Nov7.mp4

Class 22: Graphs

November 9, 2022

• Presentation (pdf) [click here]
• Recording (mp4) Nov9.mp4

Class 23: Distance in Graphs

November 14, 2022

• Presentation (pdf) [click here]
• Recording (mp4) Nov14.mp4

Class 24: Distance and Searches in Graphs

November 16, 2022

• Presentation (pdf) Searching a Graph [click here]
• Presentation (pdf) Distance Algorithms [click here]
• Recording (mp4) Nov16.mp4

Class 25: Depth First Search Applications, Flows

November 21, 2022

• Presentation (pdf) Applications of DFS [click here]
• Presentation (pdf) Flow in Networks [click here]
• Presentation (pdf) Spanning Trees [click here]
• Recording (mp4) Nov21.mp4

Class 26: Greedy Algorithms

November 28, 2022

• Presentation (pdf) [click here]
• Presentation (pdf) [click here]
• Recording (mp4) Nov28.mp4

Class 27: Dynamic Programming 1

November 30, 2022

• Presentation (pdf) [click here]
• Recording (mp4) Nov30.mp4

Class 28: Dynamic Programming 2

December 3, 2022

• Presentation (pdf) [click here]
• Recording (mp4) Dec3.mp4

Finis