Data Structures and Algorithms I

1. Administrivia
2. Meetings
3. Grading
4. Lecture Plan
5. References

In this course, we will see how to structure data (data structures) so that complex operations (algorithms) can be efficiently executed. This course lies in the intersection of mathematics and computing. We will learn about the most basic and widely-used data structures and algorithms, prove their correctness and efficiency by writing mathematics, and implement them using C/C++ to understand how they work in practice.

1. Administrivia

If you are absent from a lecture until Exam I for any reason, fill the form of absence for ES242.

Fill this form to select your availability for labs.

2. Meetings

2.1. Nov 15

Binary search trees. Definition. Search. Running-time. Discussion on proof approaches to worst-case upper bounds and lower bounds.

2.2. Nov 13

Rehashing. Amortized analysis of insertion.

Application of linked lists: window switching.

2.3. Nov 8

Implementing hash tables.

2.4. Nov 6

Hash tables for implementing Python dictionaries.

2.5. Nov 1

Implementing stacks and queues using linked lists, tail-sharing, circular singly linked lists.

2.6. Oct 23

Linked lists. Allocation and insertion.

2.7. Oct 18

Discussion on exam 2 solutions.

2.8. Oct 9

BFS implementation for solving 8-puzzles with the minimum number of moves.

2.9. Oct 4

Queues, BFS, finding solutions to puzzles in the smallest number of steps.

2.10. Sep 27

Sudoku solving and DFS time complexity analysis.

2.11. Sep 25

DFS for path-finding and writing a sudoku solver.

2.12. Sep 20

Stacks and implementation of an RPN calculator.

2.13. Sep 18

DFS and depth-first search trees. The tictactoe algorithm is a DFS.

2.14. Sep 13

Encoding and decoding tictactoe strategy into bytes. Indexing boards.

2.15. Sep 11

4x4 tic-tac-toe. Memoization. Fibonacci numbers with memoization.

2.16. Sep 2

Exam I

2.17. Aug 30

Fixing bug in tictactoe. Use of void * in C.

2.18. Aug 28

Implementing optimal tictactoe strategy using recursion.

2.19. Aug 23

Quiz for Aug 23

Proof of correctness for permutations. Accepting function pointers for generality.

2.20. Aug 21

Quiz for Aug 21

Recursion: Towers of Hanoi, Generating all permutations.

2.21. Aug 17

Demo and support on setting up C, Git, Zulip by Reuben.

2.22. Aug 16

Quiz for Aug 16

gcdlcm function, definition of asymptotic primitives.

2.23. Aug 14

Quiz for Aug 14

Loop invariants, Time complexity of Euclid's algorithm.

Design of gcdlcm function and multiple return values.

2.24. Aug 10

Tutorial 1.

2.25. Aug 9

Quiz for Aug 9

Euclid's GCD algorithm. Termination. Correctness (GCD Theorem). Direct proofs. Proof by induction.

2.26. Aug 7

Quiz for Aug 7

Discussion on gcd. Computers vs unit-cost RAM. Execution trace and running time.

2.27. Aug 3

Quiz for Aug 3

Discussion on specification of computational problems. Algorithms. Naive GCD computation.

2.28. Aug 2

Quiz for Aug 2

General introduction to the course, policies, administrative stuff.

Attendance in a lecture until exam I will earn you 1 mark provided you attempt the live quiz and score sixty percent or above. If you attend the live quiz and score less than sixty percent, you are required to attempt until you score sixty or above. If you miss a lecture for a valid reason, you can attend the quiz at a later time and receive the marks for attendance.

3. Grading

Assessment	Percentage
Attendance	10
Lab Assignments	20
Exam I	20
Exam II	20
Exam III	30

4. Lecture Plan

#Lectures	Topic
1	Problems, Algorithms
1	Execution, Time
2	Asymptotic Analysis
2	Proofs
2	Recursion
2	Stacks
1	Queues
1	Priority queues
1	Heaps, heapsort
2	Sets, Dictionaries
1	Dynamic arrays
2	Hashing
2	Binary Search Trees
3	Graphs, Trees
2	Traversal
2	Graph algorithms
3	Reductions