Bryn Mawr College
CMSC 330 Algorithms: Design & Practice
Prof. Deepak Kumar
Lecture Hours: Tuesdays & Thursdays, 12:55p to 2:15p
Room: Park 337
Lab: Tuesdays 2:25p to 3:45p in Room 231 (Attendance in ALL labs is required)
Office Hours: Thursdays 2:30p to 4:30p, or by appointment.
- Computer Science Lab Room 231 (Science Building)
- You will also be able to use your own computer to do the labs
for this course.
Algorithms Unlocked by Thomas Cormen, MIT Press, 2013.
Nine Algorithms That Changed The Future by John MacCormick, Princeton University Press, 2013.
Course Description: This course examines the applications of algorithms to the accomplishments of various programming tasks. The focus will be on understanding of problem-solving methods, along with the construction of algorithms, rather than emphasizing formal proving methodologies. Some of the algorithms we will study/implement include: searching, sorting, search engine indexing, Page Rank, pattern recognition: nearest neighbor, decision trees, neural nets, graph algorithms, error correcting codes, data compression, digital signatures, database algorithms, cryptographic hash functions, etc. Additionally, we will learn how to measure program performance, programming pitfalls, code optimization, advanced programming structures, etc. Prerequisites: CS206 and CS231. This is a Writing Intensive (WI) course.
January 17: First lecture
April 27: Last Lecture
Unless explicitly specified, all assignments are due at the beginning of the class (BY 9:55a sharp) on the date due. No credit will be awarded for any late work.
- Lab#1 (Write-up Due in class on Tuesday, January 28): Language Standards, Reference Compilers, Programming Pitfalls
- Lab#2: (Write-up Due in class on Tuesday, February 4): Performance analysis of Linear Search algorithms.
- Lab#3: (Write-up due in class on Tuesday, Feb 11): Comparing Quicksorts: Bentley's QS, Hybrid (QS+Insertion Sort), Library sort.
- Lab#4: (Wtrite-up due in class on Tuesday, Feb 18): Special WTF Week Edition.
- Lab#5: (Wtrite-up due in class on Tuesday, Feb 25): Finding Anagrams
- Lab#6: (Wtrite-up due in class on Tuesday, March 3): Hash Tables & Hash Functions
COVID-19 Remote Mode
- Do this by March 17 at noon. Please check into Piazza and say "hi", post a pic (selfie, pet, flowers, whatever makes you happy!), and tell us where you are.
- Lab#7-8: [Week of March 16] (Submission due by e-mail on Tuesday, March 23 by 5p, Eastern): Computing Square Roots.
- Lab#9: [Week of March 23] (Submission due by e-mail on Tuesday, April 7 by 5p, Eastern): The Bryn Mawr (W-O-M-A-N) Puzzle: March to Washington, DC.
- Lab#10: [Week of April 7] (Submission due by e-mail on Tuesday, April 21, by 5p, Eastern): Dijkstra's Shortest Path Algorithm.
- Week 1 (January 21, 23)
January 21: Course introduction, logistics, overview. Agorithms: Truth, Beauty, and Engineering. Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).
Read: Chapter 1 from Cormen, Chapter 1 from MacCormick.
Lab#1 Language Standards, Reference Compilers, Programming Pitfalls. Write-up is due in class on Tuesday, January 28
Slides: Introduction to Algorithms - Part 1
January 23: Algorithms: A Bird's Eye View (What is an algorithm, information processing, problem solving, models, solvability, computability, complexity and complexity classes, time complexity).
Read: Chapter 1 from Cormen, Chapter 1 from MacCormick.
- Week 2 (January 28, 30)
January 28: Discussion of Lab#1. Algorithms for linear search. Doing performance analysis.
Read: Chapter 2 & 3 from Cormen.
Lab#2: (Write-up Due in class on Tuesday, February 4): Performance analysis of Linear Search algorithms.
January 30: Sorting algorithms (Chapter 3 from Cormen) - Presentation by: Lipi & Ruby.
Read: Chapter 2 from MacCormick.
- Week 3 (February 4, 6)
February 4: Performance Analysis of Linear Search algorithms - Presentation by: Abbie & Sonya. Bentley's Quicksort, Hybrid (Quicksort+Insertion Sort).
Read: Chapter 2 from MacCormick.
Lab#3: (Write-up due in class on Tuesday, Feb 11): Comparing Quicksorts: Bentley's QS, Hybrid (QS+Insertion Sort), Library sort.
February 6: Search Engine Indexing (Chapter 2-McCormick) - Presentation by: Jocelyn & Julia.
- Week 4 (February 11, 13)
February 11: Lab#3 Comparing Quicksorts - Presentation by: Emily & Tanjuma.
Lab#4: (Wtrite-up due in class on Tuesday, Feb 18): Special WTF Week Edition.
Also, in honor of WTF Week, check out these archives from the past: Ashley Gavin's Data Structures in Python rap, JD's recursion song.
February 13: PageRank (Chapter 3 - MacCormick) - Presentation by Sophia & Yupei.
Read: Chapter 4 from MacCormick and Chapter 8 from Cormen.
- Week 5 (February 18, 20)
February 18: Lab#4 Presentation by: Nisha & Zainab.
Lab#5: (Wtrite-up due in class on Tuesday, Feb 25): Finding Anagrams
February 20: Public Key Cryptography (Chapter 4 - MacCormick, Chapter 8 - Cormen) - Presentation by: Allison, Jenny & Eun Soo.
- Week 6 (February 25, 27)
February 25: Lab#5 Finding Anagrams - Presentation by: Mahika & Milli.
Lab#6: Hash Tables & Hash Functions
February 27: Pattern Recognition: Nearest neighbor, Decision Trees (Chapter 6-MacCormick) - Presentation by Abbie & Zainab. Deepak: Decision Trees - ID3 Algrotithm.
- Week 7 (March 3, 5)
March 3: Lab#6 Hash Tables & Hash Functions - Presentation by: Yupei & Julia. Deepak: Graphs and Graph Algorithms. Topologicat Sort.
Read: Chapter 6 from MacCormick), Chapter 5 from Cormen.
No Lab this week.
March 5: Pattern Recognition - Neural Nets (Chapter 6 - MacCormick) - Presentation by Mahika & Sonya
Read: Chapter 6 from Cormen.
- Week 8 (March 10, 12)
No classes. Spring Break!
- Week 9 (March 17, 19) COVID-19 - We have gone remote.
Graph Algorithms (Dijkstra's Shortest Path) - Presentation by Nisha & MilliDo this by March 17 at noon. Please check into Piazza and say "hi", post a pic (selfie, pet, flowers, whatever makes you happy!), and tell us where you are.
Lab#7:Soundex and Metaphone
Community Day of Learning. No class. Lab#7-8: [Week of March 16] (Submission due by e-mail on Tuesday, March 23 by 5p, Eastern): Computing Square Roots.
Journal Topic for this week: Algorithms in my life.
- Week 10 (March 24, 26)
Lab#7: Soundex and Metaphone - Presentation by Allison & Sophia
Graph Algorithms - Part 1
Lab#9: [Week of March 23] (Submission due by e-mail on Tuesday, April 7, by 5p, Eastern): The Bryn Mawr (W-O-M-A-N) Puzzle: March to Washington, DC..
Data for Lab9: http://cs.brynmawr.edu/Courses/cs330/spring2020/USStates.csv
Study Material: Blind Search: Depth-First and Breadth-First Search (Powerpoint presentation w/ voice over).
Journal Topic for this week: My Favourite Algorithm.
Graph Algorithms: Bellman Ford Algorithm - Presentation by Emily, Jenny, and Tanjuma
- Week 11 (March 31, April 2)
Lab#8: Graph Algorithms: Floyd Warshall Algorithm)- Presentation by Eun Soo and Lipi
Graph Algorithms - Part 2
Journal Topic for this week: Most Challenging Algorithm.
Error Correcting Codes (Chapter 5 MacCormick) Presentation by
- Week 12 (April 7, 9)
Lab#9 Graph Algorithms - Part 2 - Presentation by Ruby & Jocelyn
Computing Fibonacci Numbers in Python
Lab#10: [Week of April 7] (Submission due by e-mail on Tuesday, April 21, by 5p, Eastern): Dijkstra's Shortest Path Algorithm.
Data for Lab9: tinyEWD.txt, mediumEWD.txt
Study Material: Dijkstra's Shortest Path Algorithm (10:51min): Video on Computer Science Channel by Kevin Drumm.
Journal Topic for this week: Programs = Abstract Data Types + Algorithms
Data Compression (Chapter 9 Cormen, Chapter 7 MacCormick) - Presentation by
- Week 13 (April 14, 16)
April 21: Hope you are all doing well and staying healthy. Please make sure you have started and finished your Lab#10, Task#1 by now.
Journal Topic for this week: My Goto Programming Language(s)
NEW: A hand trace of Dijkstra's Shortest Path algorithm (PPT with voice over, <35 min)
A handout for doing pen and paper tracing of Dijkstra's Algorithm (pdf)
April 23: Hope you are all doing well and staying healthy.
- Week 14 (April 21, 23)
Lab#11: Cryptographic Hash Functions - Presentation by
Journal Topic for this week: My Next Programming Language
Lab#12: Data Compression: LZW Algorithm
Digital Signatures (Chapter 9 - MacCormick) - Presentation by
- Week 15 (April 28, 30)
Lab#12: Data Compression: LZW Algorithm - Presentation by
Journal Topic for this week: Algorithms: Design & Practice
April 30: Course Wrap up.
Punctual Attendance and active participation are
expected in every class. Anyone arriving later than 1:00p will be considered absent for that class. Participation includes asking questions,
contributing answers, proposing ideas, and providing constructive
comments. 30% of your course grade (see below) is based on attendance & participation.
As you will discover, I am a proponent of two-way communication
and I welcome feedback during the semester about the course. I am available to answer student questions, listen to concerns, and
talk about any course-related topic (or otherwise!). Come to
office hours! This helps me get to know you. You are welcome to
stop by and chat. There are many more exciting topics to talk
about that I won't have time to cover in-class.
stay in touch with me, particularly if you feel stuck on a topic
or project and can't figure out how to proceed. Often a quick
e-mail, or face-to-face conference can reveal solutions
to problems and generate renewed creative and scholarly energy. It
is essential that you begin assignments early.
All graded work will receive a grade, 4.0, 3.7, 3.3, 3.0, 2.7, 2.3, 2.0, 1.7, 1.3, 1.0, or 0.0. At the end of the semester, final grades will be calculated as a weighted average of all grades according to the following weights:
Labs & Written Work: 35%
Class Participation: 20%
Incomplete grades will be given only for verifiable medical
illness or other such dire circumstances. Please have any instances of medical illness or dire circumstances communicated to me thorugh your Dean.
Submission, Late Policy, and Making Up Past Work
All work must be turned in either in hard-copy or electronic
submission, depending on the instructions given in the
assignment. E-mail submissions, when permitted, should request
a "delivery receipt" to document time and date of submission.
Extensions will be given only in the case of verifiable medical
excuses or other such dire circumstances, if requested in advance
and supported by your Academic Dean.
No assignment will be
accepted after it is past due.
No past work can be "made up" after it is due.
No regrade requests will be entertained one week after the graded work is returned in class.
I encourage you to discuss the material and work together to
understand it. Here are some thoughts on collaborating with other
If you have any questions as to what types of collaborations are
allowed, please feel free to ask.
- The readings and lecture topics can be group work. Please discuss
the readings and associated topics with each other. Work
together to understand the material. I highly recommend forming
a reading group to discuss the material -- I will explore many
ideas and it helps to have multiple people working together to
- It is fine to discuss the topics covered in the homeworks, to
discuss approaches to problems, and to sketch out general
solutions. However, you MUST write up the homework answers,
solutions, and programs individually without sharing specific
solutions, mathematical results, program code, etc. If you
made any notes or worked out something on a white board with
another person while you were discussing the homework, you
shouldn't use those notes while writing up your answer.
- Under ABSOLUTELY NO circumstances should you share computer
code with another student, printed, electronic, or otherwise. Similarly, you are not
permitted to use or consult code found on the internet for any
of your assignments.
Created on January 3, 2018.