CSE 464/564: Algorithms (Spring 2018)

Vaskar Raychoudhury

Lectures: 

CSE 464/564- A         71347/71354 Class      10:05 am-11:25 am  [Tuesdays & Thursdays]

CSE 464/564- B          81930/81931 Class      1:15 pm-2:35 pm     [Tuesdays & Thursdays]

Venue: BEN 213

Office Hours: Tuesdays & Thursdays 2:35 - 4:30 pm (seek appointment for other urgent requirements)

 

Notice(s)

 

                                                                                                                                                                                                                                                                                                                                           Last Modified: 02.15.2018

02.15.2018 => Starting from Feb. 27, 2018, every Tuesday there will be a class quiz to evaluate the immediate past week's studies

02.13.2018 => On Thursday (February 15, 2018) class there will be a class quiz on all previous topics covered. It will be graded.

02.12.2018 => Problem definition for Group Project must be submitted by Feb. 22, 2018. Please show your problem definition to the Instructor SEVERAL Times before final submission.

02.12.2018 => Several deadlines for Group Project has been uploaded (along with the points) in a file format

02.12.2018 => Assignment 1 is uploaded in Canvas. Due date for hard copy submission is during class time on Feb. 22, 2018.

02.05.2018 => Students who do not submit project groups and topics by 02.06.2018 will be assigned NO MARKS for the project component

02.05.2018 => Please do the readings before coming to class and go through the notes from last lecture

01.30.2018 => Welcome to the Algorithms (CSE-464/564) class    

 

Welcome to the Spring 2018 CSE 464/564 course web page. This course teaches techniques for the design and analysis of efficient algorithms, emphasizing methods useful in practice. Topics covered include: sorting; search trees, heaps, and hashing; divide-and-conquer; dynamic programming; graph algorithms; shortest paths; network flow; etc. This course is an extremely important fundamental course for CSE students.

More Detailed Course Info.

Group Projects

 

Course Schedule and TimeTable

Week/Cl.#

Date

Lecture

Readings

Assignments

1/1

Jan. 30, 2018

Class Induction;Introduction to Design & Analysis of Algorithms; Revision of Pre-requisites; Basics of Graphs

Class Notes + CORMEN B.4, B.5

 

1/2

Feb. 01, 2018

Insertion Sort and Merge Sort and their complexity analysis

Class Notes + CORMEN 2.1, 2.2 and 2.3

 

2/3

Feb. 06, 2018

Asymptotic Notation; Solving related problems, Recurrences: Recursion Tree Method

Class Notes + CORMEN Chapter 3, 4.4

 

2/4

Feb. 08, 2018

Recurrences: Substitution Method, Master Method; Solving Problems

Class Notes + CORMEN  4.3 and 4.4

Problem Set 1 given. Turn in by 02/22/2018. 

3/5

Feb. 13, 2018

Recurrences: Master Method, Divide and Conquer I: Binary Search, Powering a Number

 Class Notes + CORMEN 4.5

 

3/6

Feb. 15, 2018

Divide and Conquer II: Quick Sort and its complexity analysis

Class Notes + CORMEN 7.1 and 7.2 

 

4/7

Feb. 20, 2018

Heap Sort, Priority Queue

Class Notes + CORMEN Chap. 6

 

4/8

Feb. 22, 2018

Greedy Algorithms I: Minimum Spanning Tree, Properties of Greedy Algorithms 

Class Notes + CORMEN 23.1

 

5/9

Feb. 27, 2018

Greedy Algorithms II: Prim's Algorithm for MST

Class Notes + CORMEN 23.2 (pp. 634-36)

 

5/10

Mar. 01, 2018

Greedy Algorithms III: Shortest Paths: Dijkstra's Algorithm

Class Notes + CORMEN 24.3

 

6/11

Mar. 06, 2018

Greedy Algorithms IV: Maximum Flow: Ford-Fulkerson Algorithm

Class Notes + CORMEN 26.1, 26.2

Problem Set 2 given. Turn in within 1 week.

6/12

Mar. 08, 2018

Dynamic Programming I: Rod-cutting Problem

Class Notes + CORMEN 15.1

 

7/13

Mar. 13, 2018

Dynamic Programming III: Longest Common Subsequence Problem

Class Notes + CORMEN 15.4

7/14

Mar. 15, 2018

Fractional Knapsack Problem, 0/1 Knapsack Problem

Class Notes + CORMEN 16.2 (pp. 425-427)

Mid-Term Exam

8

 

SPRING BREAK

 

 

9/15

Mar. 27, 2018

Breadth First Search (BFS)

Class Notes + CORMEN 22.2

9/16

Mar. 29, 2018

Depth First Search (DFS)

Class Notes + CORMEN 22.3

10/17

Apr. 03, 2018

Topological Sort; Strongly Connected Components (SCC )

Class Notes + CORMEN 22.4, 22.5

 

10/18

Apr. 05, 2018

String Matching Algorithms I: Rabin Karp

Class Notes + CORMEN 32.2

 

11/19

Apr. 10, 2018

String Matching Algorithms II: Knuth-Morris-Pratt

Class Notes + CORMEN 32.4

Problem Set 3 given. Turn in within 1 week. 

11/20

Apr. 12, 2018

Advanced Data Structure I: Hash Tables

Class Notes + CORMEN 11.2, 11.3

12/21

Apr. 17,  2018

Advanced Data Structure II: Red-Black Trees

Class Notes + CORMEN 13.1-13.4

 

12/22

Apr. 19, 2018

NP-completeness I: P, NP, NP-hard, and NPC

Class Notes

 

13/23

Apr. 24, 2013

NP-completeness II: NP-hard / NPC Problems: Boolean SAT, SAT, 3-SAT

Class Notes

 

13/24

Apr. 26, 2013

NP-completeness III: NP-hard / NPC Problems: Max Independent Set, Max Clique, Vertex Cover

Class Notes

 

14/25

May 01,2013

NP-completeness IV: NP-hard / NPC Problems: Graph Coloring, Hamiltonian Cycle

Class Notes

 

14/26

May 03,2013

Probabilistic Analysis and Randomized Algorithms

 

 

15/27

May 08, 2013

 

 

15/28

May 10, 2018

 

 

End-Term Exam

* Keep checking course website for new information