Basic Algorithms, Summer 2024, CSCI-UA.0310- 001

Key information

·       Class Meetings: Tuesdays and Thursdays, 2:10-4:15 pm, online via Zoom (see Brightspace for class link)

·    Midterm Exam: July 2, 2024, 2:10-4:15 pm, Zoom link on Brightspace

·    Final Exam: Aug 15, 2:10-4:15 pm, Zoom link on Brightspace

·    Instructor: Areeba Ikram; student drop-in hour Thursday 4:15 pm-5:15 pm, Zoom link on Brightspace, additionally by appointment

·    Tutors and tutoring hours (Zoom links are on Brightspace):

· Utkarsh – Monday 2-5 pm, Tuesday 4:30-7:30 pm, Friday 10 am-12 pm

                    (Monday and Tuesday also in person, 230 CIWW)

· Vamshi – Wednesday 3-5 pm, Thursday 9-11 am

Overview

Reviews several important algorithms, with emphasis on correctness and efficiency. The topics covered include solving recurrence equations, sorting algorithms, binary search trees, partitioning, graphs, spanning trees, shortest paths, connectivity, depth-first and breadth-first search, dynamic programming, and divide-and-conquer techniques. The somewhat ambitious plan is to cover (most of) chapters 1-4, 6-8, 12, 15, 16, 22-25, 30, 31, 34 of [CLRS] (see below).

Prerequisites

At least one year of experience with a high-level language such as Pascal, C, C++, or Java; familiarity with recursive programming methods and data structures (arrays, pointers, stacks, queues, linked lists, binary trees).

Resources

·       Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein, published by MIT Press. Our main textbook. 

·    Algorithm Design by Jon Kleinberg and Eva Tardos, Published by Pearson.

·    Lecture Slides for Algorithm Design by Kevin Wayne, distributed by Pearson. See the Brightspace page for accessible versions of these slides.

 

 

Notes, assignments, and other course materials will be posted on the course Brightspace page.

 

Summary of lectures (tentative)

Week

Dates

Topics

Read and watch before class

1

May 21, 

May 23

Intro, logistics, insertion sort, run time analysis, Big-O notation, merge sort,

Analysis of merge sort, Quick Sort

CLRS §1, §2.1, §2.2; Insertion sort video and demo (click INS)

CLRS §2.3,3; Merge Sort video and demo (click MER); Big-O video

CLRS §2.3, 4.3-4.6, 7; Quick Sort video and demo (click QUI)

2

May 28,

May 30 

 

Finishing Quick Sort; Karatsuba's algorithm, Closest pair in the plane

CLRS §7, KT §5, CLRS §33.4

3

June 4,

June 6

 

 

Median and order statistics in linear time; Lower bound for comparison sort

 

CLRS §9,

CLRS §8.1

4

June 11,

June 13

Counting sort, Radix sort; Dynamic Programming: Fibonacci 

Numbers, Rod Cutting Problem

CLRS §8.2, §8.3,

CLRS §15.1

5

June 20

(No class June 18 – Legislative Wednesday – classes meet according to Wednesday schedule)

Dynamic Programming: Longest Common Subsequence, Knapsack

 

 

CLRS §15.4, visualization

CLRS §15.3-4; Demaine's video lecture

6

June 25, 27

 

 

 

 

Dynamic Programming continued;

Catch-up/review

 

 

7

July 2

 

(No class July 4 -  Independence Day)

Midterm Exam

8

July 9, 

July 11

 

 

Greedy: Activity selection (aka interval scheduling)

 

Greedy - Huffman Code,

Graphs, BFS

 

CLRS §16.1-2,

6 first minutes of video on priority queues; CLRS §16.3,

CLRS §22.1-22.2, adj list and adj matrix visualization, visualization

9

July 16,

July 18

DFS, edge classification, detecting acyclic graphs,

Topological sort, strongly connected 

components

CLRS §22.3; video

 

CLRS §22.4,22.5

10

July 23,

July 25

Finishing SCC; Minimum Spanning Tree

MST safe edge theorem, Kruskal's algorithm

Prim's algorithm

CLRS §23.1; demo

 

CLRS §23.2

11

July 30,

August 1

 

 

Dijkstra's SSSP algorithm, Floyd-Warshall APSP algorithm,

Computability, Wang tiling, the halting problem is uncomputable

CLRS §24.3 and video,

CLRS §25.2, CLRS §34

12

August 6,

August 8

P vs. NP, NP-completeness, Vertex Cover, Independent set, 3SAT, reductions, approximating Vertex Cover

CLRS §34, 35

13

 

 

August 13

 

 

August 15

Catch-up/review

 

 

Final Exam

 

Course Policies

Homework

There will be weekly homework assignments. We prefer homework submissions typeset in LaTeX (you might want to use the Overleaf templates) or Word. You are encouraged to insert scanned figures or illustrations. Scanned handwritten submissions will only be graded if neatly written and perfectly legible. Honors questions will be graded but will not affect your grade. Submission is through Gradescope

The written assignments will require rigorous solutions which give clear and straightforward explanations. Each answer will be judged on the explanation’s clarity, correctness, and conciseness. A design of an algorithm requires proof of correctness and proof of runtime for full credit, along with a clear explanation of the algorithm. You will receive zero credit for the answer if you write pseudocode without any explanation. 

Grading

The tentative grade split is 5% participation, 40% homework, 25% midterm, and 30% final exam.

Late Submission Policy

Late submissions of homework solutions will be graded with a 20% penalty per day of late submission. Solutions will not be graded if submitted later than 48 hours after the specified deadline.

Academic Integrity

Please review the departmental academic integrity policy.

Collaboration

We strongly encourage you to discuss assignments with your peers. However, all work that you submit must be your own. You must list all discussions you had.  For each solution that you discussed or looked at extra materials for hints, you must mention it in your solution. This will not incur any penalty, but if noticed otherwise by the graders, it might question your academic integrity, and there might be more severe repercussions.
For most other incidents, the standard CIMS academic integrity policy applies. 

You should not consult previous years' students, code, assignments, etc. You may help other students and groups on specific technical issues, but you must acknowledge such interactions.

Plagiarism

Anything you use from other sources (other students, web, etc.) must be acknowledged. Failure to do so will result in a zero grade for the submitted work and, except in cases of obvious mistakes, a University investigation.

Participation

Students are expected to attend every meeting of the class. Students are also expected to participate actively in course discussions. Participation will be taken into account in the final grade. Details on how participation will be figured into the grade can be found on the Brightspace page.

Third-Party Software

In this class, we will be using Desmos classroom activities. The use of this software is for educational purposes only. This third-party software is not an NYU-supported service with data privacy, FERPA, and security protections in place (like your NYU Gmail, NYU Brightspace, etc.). I will structure assignments so that no highly sensitive information is needed to use the tool, but please note that we are subject to the terms of use set by the platform's developer https://www.desmos.com/terms  If you have any concerns about the platform, please let me know as soon as possible.

 

 

Applicable University Policies

Academic Integrity

The work you submit should be your own. Please consult the CAS academic integrity policy for more information. Penalties for violations of academic integrity may include failure of the course, suspension from the University, or even expulsion.

Religious Observance

As a non-sectarian, inclusive institution, NYU policy permits members of any religious group to absent themselves from classes without penalty when required for compliance with their religious obligations. The policy and principles to be followed by students and faculty may be found in the University Calendar Policy on Religious Holidays.

Disability Disclosure Statement

Academic accommodations are available to any student with a chronic, psychological, visual, mobility, learning disability, deaf, or hard of hearing. Students should please register with the Moses Center for Students with Disabilities at 212-998-4980.

NYU's Henry and Lucy Moses Center for Students with Disabilities

726 Broadway, 2nd Floor

New York, NY 10003-6675

Telephone: 212-998-4980

Voice/TTY Fax: 212-995-4114

Web site: http://www.nyu.edu/csd