Course: CSE 582: Data Structures and Algorithms

State University of New York at Stony Brook, Fall 2024

Classes	MoWe 9:30AM - 10:50AM, LGT ENGR LAB 102 WESTCAMPUS
Instructor	Prof. Pramod Ganapathi Office hours: MoWe 03:25PM - 04:55PM, Room 105 New Computer Science
TA's	Google sheets
Note	This course is mainly for satisfying the prerequisites of algorithms and data structures. It will NOT count as a lecture course for CS M.S. students. It will NOT count towards CS Ph.D. quals. However, its credits will count for graduation for both CS M.S. and CS Ph.D.

Course Description	The course consists of two parts. The first part covers data structures to efficiently store, organize, modify, and access data. Topics include: arrays, stacks, queues, linked lists, trees, hash tables, priority queues, and graphs. The second part covers the design and analysis of algorithms for solving computer science problems. Topics include: algorithm analysis, exhaustive search algorithms, divide-and-conquer algorithms, greedy algorithms, and dynamic programming algorithms.
Prerequisites	Programming experience in at least one high-level programming language and competence in using programming tool chains (writing, compiling, running and debugging programs). Most part of the course will not require coding. We might have one or two instances where we might have coding questions; you will have to use Java programming language in such cases The data structures topics will have example codes in Java.
Credits	3
Course Outcome	At the end of the course, the students should have the following knowledge, skills, and wisdom: An understanding of the design and analysis of several fundamental data structures and algorithms An understanding of when, how, and why different algorithm design techniques are used An ability to use apt design techniques and efficient data structures to design efficient algorithms
Textbooks	[AL] Introduction to the Design and Analysis of Algorithms (3rd Edition). Anany Levitin. [GTG] Data Structures and Algorithms in Java (6th Edition). Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser. (Source codes and PDF handouts can be found here) [MAP] Mathematical and Algorithmic Puzzles. (This book shows how mathematical ideas and algorithmic techniques can be used to solve beautiful puzzles.)
Grading	Course requirements and grading are as follows: Homework: 10% Midterm: 30% Final: 60% A list of problems helpful for exams are below: Data Structures Algorithms
Homework	Homework will be posted on Brightspace. Homework must be written on plain sheets of paper, scanned using a good scan app, and a single scanned PDF must be submitted on Brightspace. Homework can also be written using Word or Latex or a tablet. The PDF must have the student ID as the file name. Late submissions will not be graded for any reason (including oversleeping, forgetting, PC issues, technical issues, Brightspace issues, traveling, etc), except in the case of medical emergencies (with documentation submitted to and verified by the Student Support Team) and on the discretion of the instructor based on a case-by-case basis. It is strongly recommended to submit at least one version three days before the deadline. A student can submit an infinite number of versions of the answer sheets PDF to the Brightspace. We only evaluate the last/final version of the solutions PDF uploaded on Brightspace before the deadline. Students should not submit the first version of their homework at the exact deadline or later or a few seconds/minutes just before the deadline. Because, we do not consider the time at which a homework was submitted, we consider the time at which the homework was successfully up on Brightspace (with all pages in human-readable form) and it takes a few seconds/minutes to upload on Brightspace. If Brightspace flags the homework as late, it is late. Regrade requests deadline is 1 week after getting the homework/exam results on Brightspace.
Makeup Exams	Makeup exams will not be given for any reason (including oversleeping, forgetting, PC issues, technical issues, Brightspace issues, traveling, etc), except in the cases of medical emergencies (with documentation submitted to and verified by the Student Support Team) and on the discretion of the instructor based on a case-by-case basis; student participation in university sponsored events (with documentation); and religious absences (with documentation).
Attendance	Students are expected to attend every class, report for examinations and submit major graded coursework as scheduled. If a student is unable to attend lecture(s), report for any exams or complete major graded coursework as scheduled due to extenuating circumstances, the student must contact the instructor as soon as possible. Students may be requested to provide documentation to support their absence and/or may be referred to the Student Support Team for assistance. Students will be provided reasonable accommodations for missed exams, assignments or projects due to significant illness, tragedy or other personal emergencies. In the instance of missed lectures or recitations, the student is responsible for reviewing posted slides, reviewing recorded lectures, seeking notes from a classmate, etc. Please note, all students must follow Stony Brook, local, state and Centers for Disease Control and Prevention (CDC) guidelines to reduce the risk of transmission of COVID. For questions or more information click here.
Additional Resources	Books/Websites VisualAlgo. [SS] The Algorithm Design Manual (2nd Edition). Steven S. Skiena [PDV] Algorithms (1st Edition). Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani [JE] Algorithms. Jeff Erickson [CLRS] Introduction to Algorithms (3rd Edition). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein Interview Problems Data Structures. GeeksForGeeks. Algorithms. GeeksForGeeks. Algorithms. LeetCode. Algorithms. CodeChef. Programming Problems. TechieDelight. Problems on Algorithms (2nd Edition). Ian Parberry and William Gasarch. Proving Correctness and Analyzing Complexity. Minko Markov. Video Courses Easy to Advanced Data Structures. William Fiset. Data Structures. Steven. Algorithms: MIT Course 2015. Erik Demaine, Srini Devadas, and Nancy Lynch. Algorithms: MIT Course 2011. Erik Demaine and Srini Devadas. The Design and Analysis of Algorithms: Stanford University Course. Tim Roughgarden. Algorithms I: Princeton University Course. Robert Sedgewick and Kevin Wayne. Graph Algorithms. William Fiset. Mathematical Puzzles Wu Riddles TED-ED Puzzles 3Blue1Brown Kurzgesagt Numberphile Brainzilla LaTeX [OL] Learn LaTeX in 30 Minutes. Overleaf. [WBL] Wikibook on LaTeX. Wikipeople. [NSIL] The Not So Short Introduction to LaTeX. Tobias Oetiker. [LCN] LaTeX for Complete Novices. Nicola L. C. Talbot (More Books). [MML] More Math into LaTeX. George Gratzer. 4th Edition. [LT] LATEX Tutorials. Indian Users Group. [SIL] A Simplified Introduction to LaTeX. Harvey J. Greenberg. More Books Mathematical Writing [SMW] Mathematical Writing. Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts. [HWMS] Handbook of Writing for the Mathematical Sciences. 2nd Edition. Nicholas J. Higham. (Paid)

Academic calendar
Recorded video lectures can be accessed through Google Drive Link using @stonybrook.edu email account.

Lectures	Class Schedule	Slides	Study	Learning Materials
1 session	Introduction (Course Info)	[PDF]	[AL Ch. 1][GTG Ch. 1, 2]	Map of Math, Map of CS
1 session	Algorithm Code, Asymptotic Analysis	[PDF], [PDF]	[GTG Ch. 4][AL Ch. 2]
3 sessions	Arrays and Lists	[PDF]	[GTG Ch. 3, 7]
1 session	Stacks, Queues, and Dequeues	[PDF]	[GTG Ch. 6]
1.5 sessions	Recursion	[PDF]	[GTG Ch. 5]
2.5 sessions	Trees	[PDF]	[GTG Ch. 8, 11]
1 session	Hashtables	[PDF]	[GTG Ch. 10]	Chaining, Open Addressing
1 session	Priority Queues	[PDF]	[GTG Ch. 9]
Oct 09	Midterm			Time: Class time, Venue: Class Syllabus: All topics covered to this date
1.5 sessions	Brute Force	[PDF]	[AL Ch. 3]	DFS, BFS
1.5 sessions	Decrease-and-Conquer	[PDF]	[AL Ch. 4, GTG Ch. 14]	Insertion Sort, Topological Sort
3 sessions	Divide-and-Conquer	[PDF]	[AL Ch. 5]	Mergesort, Median Finding
4 sessions	Dynamic Programming	[PDF]	[AL Ch. 8]	Fibonacci, LCS, Edit Distance, APSP, Knapsack, Text Justification, More DP
2 sessions	Greedy Technique	[PDF]	[AL Ch. 9]	MST, Dijkstra
2 sessions	Backtracking	[PDF]	[AL Ch. 12]	Subsets
1 session	Algorithmically Hard Problems	[PDF]	-	Erik Demaine's Complexity I, Complexity II, Michael Sipser's P vs. NP Problem, Avi Wigderson's P vs. NP Problem, Complexity Zoo
Dec 11 (We)	Final			Time: 11:15-1:45 PM, Venue: Class, Schedule Syllabus: All topics

Academic Integrity	Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at https://www.stonybrook.edu/commcms/academic_integrity/. Students are allowed/encouraged to: learn the subject from any book/website/video/resource in the world contact TAs/instructor to understand the subject matter discuss generic ideas and concepts related to the subject with friends/classmates Students are NOT allowed to: search for solutions for the homework/exam questions on books/websites/videos/resources discuss the homework/exam questions with friends/classmates/seniors copy homework/exam solutions from Internet/books/friends/classmates/seniors
Student Accessibility Support Center	If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact the Student Accessibility Support Center, ECC (Educational Communications Center) Building, Room 128, (631) 632-6748, or at sasc@Stonybrook.edu. They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and the Student Accessibility Support Center. For procedures and information go to the following website: https://ehs.stonybrook.edu/programs/fire-safety/emergency-evacuation/evacuation-guide-people-physical-disabilities and search Fire Safety and Evacuation and Disabilities.
Critical Incident Management	Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook. Until/unless the latest COVID guidance is explicitly amended by SBU, during Fall 2021 ''disruptive behavior'' will include refusal to wear a mask during classes.