CSCI-UA-201-011-Spring-2024

Class repo for CSCI-UA 201 011, Spring 2024. I will update this page with updates of what we covered in class as well as notes.

Schedule:

Class 1 Jan 22

Syllabus. Java review -- object oriented programming, inheritance.

Reading: Chapter 2.1, 2.2, 2.6.

Class 2 Jan 24

Finish Java review -- casting, dynamic binding, abstract classes and interfaces. List ADT and started ArrayList implementation.

Reading: Chapter 2.3, 2.5, Chapter 7.1.

Section 1

Java Review.

In textbook: code fragments 2.2, 2.3, 2.4. Qs 2.10, 11, 12, 13, 17, 21, 24, 25, 26, 29

Class 3, Jan 29

Finish ArrayList implementation. Limitations of ArrayList. Start LinkedList.

Reading: First part of Chapter 7.2, Chapter 3.2.

Class 4, Jan 31

Single and Doubly LinkedLists.

Reading: Chapter 3.2, 3.4.

Section 2

LinkedList practice.

In textbook: code fragments 3.19. Qs 3.5, 6, 9, 12, 17, 18, 25, 26, 27, 28

Class 5, Feb 5

Worst case complexity algorithmic analysis. Search algorithms. Started Stacks and Queues.

Reading: Chapter 4.1-4.3, 5.1.3

Class 6, Feb 7

Examples of stack applications. Started recursion.

Reading: Chapter 6 up to and including 6.2.3, but not including 6.2.2. Chapter 5.1, 5.2

Section 3

Quiz 1 (Doubly linked lists)

Algorithmic analysis, stacks, recursion.

In textbook: Uniqness problem, Qs 4.2, 3, 6, 8-19, 22-24, 29-32, 45, 54, 56; 6.1, 3-5, 7, 9, 17, 19, 21, 23, 24; and 5.1, 2, 7, 8, 11, 15-22, 24

Class 7, Feb 12

Asignment 1 (Dynamic arrays) due

Recursion, Trees definition, implementation, calculating height and depth,

Reading: Chapter 5, 8.1, 8.3

Class 8, Feb 7

Searching, positions(), and intro to Binary trees.

Reading: Chapter 8.2 - 8.4

Section 4

Quiz 2 (Searching trees)

More on recursion, and tree methods.

In textbook: Qs from chapter 5 last week and (Ignore questions about traversals) 8.1, 2, 4, 5, 11, 12, 13, 18, 19, 20, 22, 23, 27, 28 (hint: use an auxiliary variable in a recursive method), 32, 37, 42, 45, 55, 58.

Feb 19 -- President's day

Class 9, Feb 21

Asignment 2 (Adding and removing from linked trees) due

Arithmatic trees, Traversals, Map ADT

Reading: Chapter 8.2, 8.4, 10.1

Section 5

Quiz 3 (Traversals)

Traversals and more on tree methods.

In textbook: All Qs from chapter 8 last week.

Class 10, Feb 26

Map ADT, Unsorted list implementation, Hash functions, compression functions

Reading: Chapter 10.1, 10.2

Class 11, Feb 28

Collision resolutions, start Binary search trees

Reading: 10.2, 11.1

Section 6, March 1

Quiz 4 (Maps)

Maps and hash maps.

In textbook: Qs 10.1, 3, 6, 7, 10, 11, 33, 41, 61.

Class 12, March 4

Getting, adding and removing from BSTs. Balanced trees.

Reading: 11.1, 11.2

Class 13, March 6

Adding and removing from AVL trees

Reading: 11.3.

Section 7, March 8

Quiz 5 (BST addition and deletion)

Review for midterm

In textbook: Qs 11.1, 2, 3, 4, 5, 8, 9, 29, 33

Class 14, March 11

Midterm

Assignment 4 (Hash Maps) due

Class 15, March 13

Removing from AVL trees. Adding to (a, b) trees.

Reading: 11.5, 15.2, 15.3

Section 8, March 15

Quiz 6 (AVL deletion, (a, b) tree addition)

Bit on AVL trees and (a, b) trees. Midterm recap

In textbook: 11.17, 19, 21, 22a, 47

Class 16, March 25

Midterm review -- recursion with auxillary history variables. (a, b) tree recap.

Reading: 11.5, 15.2, 15.3

Class 17, March 27

Recursion with auxillary varibles in trees. Removing from (a, b) trees. Bit on Splay trees.

Reading: 11.5, 15.2, 15.3

Section 9, March 29

Quiz 7 (AVL code)

Recursion with auxillary varibles in trees. (Questions in Review 16)

Class 16, April 1

Quadratic sorts, recap of PriorityQueues.

Reading: 9.1, 9.2, 9.4.1, bubble sort, bogo sort

Class 17, April 3

O(nlog n) efficiecy proof. Mergesort.

Reading: 12.1, 12.3.1

Section 10, April 5

Quiz 8 (Sorting)

Sorting

In textbook: 12.6, 7, 26 -- do these questions for all the sorting algorithms we have covered

Class 18, April 8

Assignment 5 (Counting with BSTs) due

Heaps and heapsort.

Reading: 9.3.1-3, 9.4.2

Class 19, April 10

Quicksort, bucketsort, and comparison of sorting algorithms.

Reading: 12.2, 12.3.2, 12.4

Section 10, April 12

Quiz 9 (Tree sort)

Heap and Quick sort.

In Textbook: 9.3, 4, 10, 11, 12, 16, 17, 19, 20, 21, 23, 30, 34; 12.9, 10, 18, 20-23, 26, 35-37, 39, 42, 43, 46, 47

Class 20, April 15

Assignment 6 (Radix Sort) due

Graph ADT and implementations.

Reading: 14.1, 2

Class 21, April 17

Graph implementations continued. Start searching in graphs.

Reading: 14.3

Section 11, April 19

Quiz 10 (Graph implementations)

Graph implementations.

In Textbook: 14.1-11, 13, 38

Class 22, April 22

Assignment 7 (Graph implementations) due

Depth and breadth first search and variants.

Reading: 14.3

Class 23, April 24

Dijkstra's algorithm ad adaptive priority queues

Reading: 14.6

Section 12, April 26

Quiz 11 (Graph search)

Searching and other graph algorithms.

In Textbook: 14.14-17, 23, 24, 44, 51-56, 60, 63, 71

Class 24, April 29

Implicits graph search, recursive backtracking, directed acyclic graphs.

Reading: 14.5

Class 25, May 1

Finish directed acyclic graphs, implcit graph search, brief overview of minimum spanning trees.

Section 13, May 3

Quiz remakes!

Course review

Class 26, May 6

Assignment 8 (Travelling salesman) due

Text compression and search

Have a good summer!