Flesh Out Data Structures & Algorithms

Currently the only real data structures & algorithms course is Roughgarden's Algorithms course, which is light on data structures. It is also, according to the very popular Princeton algorithms course's FAQ on Coursera, not enough by itself and more on the mathematical side.

I would suggest adding the two Princeton courses prior to the Roughgarden course to really flesh out this fairly important bit of knowledge, or consider adding in OpenDSA (an interactive and comprehensive textbook) or Berkley's CS61B

@Andreilg This is a good collection of high quality resources. It now falls to us to determine which are sufficient for a student. I think you would agree that not every student needs to take all 4 courses.

OSSU uses the CS2013 for curricular guidance. (A little more about that here)

CS2013 has a section on the curricular expectations of Discrete Structure instruction. (Page 77 of the doc's numbering, page 79 of the PDF) Note: the section "Core Tier-1, Core Tier-2, Elective: What These Terms Mean, What is Required" (pdf page 32) is useful for understanding the recs.

How do the recommendations in CS2013 affect your suggestion above?

It's worth noting that Stanford is one of the case studies in CS2013 so we can actually get some help from that. Assuming that we're trying to cover the Algorithms knowledge area here, CS 161 doesn't cover the following:

The entirety of Basic Automata, Computability and Complexity (they cover it in CS 103, their Discrete Math class. Dunno if MIT's course covers it or not)
Over half of Fundamental Data Structures and Algorithms. If we assume they're covering just tier one topics in this course, just under half of tier one and all of tier two. They cover it mostly in their CS 106B course with a little in CS 103.

We'd need someone who's already learned Data Structures to look at MIT 6.042J to see if it picks up the slack that Stanford CS 161 is missing and if not, what material OSSU does not cover.

@waciumawanjohi

Alright, I've taken a close look at CS2013 and we're essentially missing a course to be equivalent to CS 106B (plus a little of CS 103, but we should be able to find a course that covers all of what we're missing in one course). The following are the CS2013 Knowledge Areas that should be covered. Three out of four are what OP is referring to.

AL/Fundamental Data Structures and Algorithms (CS 161 only covers about half)
AL/Basic Automata, Computability and Complexity (I don't think this is covered elsewhere in the core curriculum?)
PL/Object-Oriented Programming (Programming Languages is intended to serve as reinforcement, not to teach it for the first time)
SDF (Software Development Fundamentals. Everything not covered in How to Design Programs and MIT 6.0001. Much of this is what OP is referring to)

Princeton's course (by itself) isn't a good option because it assumes that you've taken a Java-based intro course rather than How to Design Programs. I don't think OpenDSA is a great option either because it's moreso intended for use as a textbook than for self-learners. I'm not sure how good it would be for the task of self-learning; it probably takes the more is better model so that instructors can pick out what they want. CS 61B seems like a good option at a glance assuming that How to Design Programs is sufficient preparation and it complements CS 161 as well as we need it to. Another option could be WPI's CS 2102 followed by Princeton's course although we still need someone to go through WPI's course and make sure it works well for self-learning. The advantage of it though is that it's actually intended to continue on from How to Design Programs and it brings those ideas into object-oriented programming. WPI operates on a quarter schedule so the course isn't as long as some other courses on the curriculum. There are probably other good options too; the primary purpose of this comment is to say that on a CS2013 level, OP is correct and we are missing a course. @waciumawanjohi Should I make a Request For Comment post?

"Princeton's course (by itself) isn't a good option because it assumes that you've taken a Java-based intro course rather than How to Design Programs. "

I haven't take the Princeton course, but the old course we had assumed that you've programmed before from HtDP, but then throws Java code at you without teaching you anything about it. I think this approach is good, and gives people a chance to learn a language on the fly, or at least the parts that they need to know about for the given task / education goals.

Has anybody taken the princeton course to see if it is comparable to our old Software Construction class? At least comparable with how much you actually need to know Java before starting?

Hey, since I remember some considerations about creating along the curriculum which has not necessarily free-only courses included, I'd be interested in opinions about how something like https://www.edx.org/micromasters/ucsandiegox-algorithms-and-data-structures goes along the rest of the curriculum if one aims at more data science related knowledge of algorithms. I've copied "what you'll learn" and "syllabus" sections from all of the courses in the micromasters for a quick comparison here. Thank you in advance.

what about Algorithm and Data structure Specialization on Coursera by UCSanDiego ?

Those appear to be alternatives to Stanford's course rather than a course to fill the gap before Stanford

Those appear to be alternatives to Stanford's course rather than a course to fill the gap before Stanford

what is the gap exactly the prerequisite for those course and stanford course is discrete math and programming language or am i miss something ?

@Alaharon123

@Alaharon123 You're right. I don't know yet how or in which point does it play the role as some prerequisite to any class on algorithms or advanced data structures from MIT specifically, but there is a series of two courses on Automata, Computability, and Complexity and Computation theory from MIT.

As I have found basic data structures are taught together with introductory level algorithms in MIT's 6.006 Introduction to Algorithms. This course is the first part of a three-course sequence.

The sequence continues in 6.046J Design and Analysis of Algorithms.

The third in a sequence is 6.854J / 18.415J Advanced Algorithms

The second course in the above algorithms sequence serves as a prerequisite for the 6.851 Advanced Data Structures.

@ola-sk

@mohamedspicer Read the whole thread

@ola-sk A required Theory of Computation course is probably more hardcore than we need. For example, Williams College is in cs2013 as an example school and they have a Theory of Computation course and it doesn't cover much of the core knowledge areas aside from this Basic Automata, Computability and Complexity. They say right after that that they're thinking they should make that course an elective and put this stuff into a new Discrete Math course alongside the rest of the curriculum for that course (although they didn't actually follow through on that, which is interesting).

6.006 does look like a course to consider to fulfill the gap this issue is about. It seems to cover a large amount of the first two of #664 (comment)

Gonna post another suggestion here. Going with Princeton's Algorithms course, we could replace Intro CS with Princeton's Computer Science: Programming with a Purpose and Computer Science: Algorithms, Theory, and Machines as a prerequisite.

Pros:

Covers pretty much exactly what we need.
Works well as a survey course, which is the goal of Intro CS

Cons:

We don't know the course's quality
It is a university course like 6.0001 and cs50 so it's hard and may require looking at outside resources
You'd be learning Java before How to Design Programs (HtDP) when HtDP is ideally supposed to lead into Java as outlined in Developing Developers
Math-heavy according to this Reddit comment (although it only requires high school math probably to the level of pre-calculus, possibly even only algebra 2)

@Alaharon123

CS61A IIRC has all materials available for public. This would make a great intro course.
CS61B spring 2018 version has the gradescope also available for the public last I checked. I think this will be useful for grading oneself on the assignments. CS61B uses its own online text and also references Algorithms by Sedgewick.
@Alaharon123 I have gone through the 2 princeton courses that you have linked. I can vouch that the quality is very high. The quality of the books is also very high. Additionally, for the courses we have a booksite which has a short version of the textbook itself, many textbook problems (and solutions for many) and additional exercises too. The only con I found is the similar to the reddit comment - it approaches CS/programming from a science/engineering/applied math perspective than from a programmer's perspective. You can expect a lot of questions trying to implement mathematical formulae (which I'm not saying is bad, it does make you think) but it will be very abstract for many people.

For anyone starting out CS/programming, personally I suggest the following sequence of courses - Intro to CS -> Data Structures -> Intro to Systems. I have found HtDP to be a good resource, but it gets tedious when you continue to go through it. I think HtDP would serve well with its successor PAPL.

CS61A -> CS61B -> CS61C / CSAPP from CMU (15213)
Princeton Intro -> Princeton Algorithms -> CSAPP from CMU (15213)

To follow up with algorithms, I think the stanford course would do quite well after CS61B / Princeton Algorithms course. A firm grounding on data structures would help in getting more out of the Algorithms course.

An excerpt from the Algorithms book by Sedgewick

Context The book is intended to follow our introductory text, An Introduction to Programming in Java: An Interdisciplinary Approach, which is a broad introduction to the field. Together, these two books can support a two- or three-semester introduction to computer science that will give any student the requisite background to successfully address computation in any chosen field of study in science, engineering, or the social sciences.The starting point for much of the material in the book was the Sedgewick series of Al-gorithms books. In spirit, this book is closest to the first and second editions of that book, but this text benefits from decades of experience teaching and learning that material. Sedgewick’s current Algorithms in C/C++/Java, Third Edition is more appropriate as a reference or a text for an advanced course; this book is specifically designed to be a textbook for a one-semester course for first- or second-year college students and as a modern introduction to the basics and a reference for use by working programmers.

@Andreilg thank you for mentioning the TOC resource. It seem wonderful companion to the Sipser book.

This is covered in Theory of Computation in OSSU already.

That's in Advanced CS where you only need to take a subset of the courses. It does cover the material, but in significantly more depth. For example, in the Princeton sequence, pretty much all that needs to be covered is in weeks 4-6 of Computer Science: Algorithms, Theory, and Machines and Regular Expressions part of week 5 and Intractability part of week 6 of Algorithms, Part II

Yea, honestly why don't we just use CS 61B?

Indeed. When there's a Request for Comment, that will be one of the options presented in the body text.

I still really think we should have the Princeton Algorithms course (Parts 1 & 2) followed by the Roughgarden course as mandatory for a full coverage of algorithms from different angles. They're clearly complementary to each other. And probably CS 61B before it.

Can you elaborate further on why you'd have both 61B and these two other courses? Wouldn't 61B have a lot of overlap with them?

I think HtDP would serve well with its successor PAPL.

Worth noting that FunctionalCS has links to lectures for Brown CS 0190 (besides for the already freely available homeworks and labs), which covers PAPL and only requires a subset of HtDP as preparation.

Intro to CS with Princeton (both courses) look good from the syllabus, but I haven't taken them. I especially like that the second one goes into theory (turing machines, etc) which we don't currently have in Core CS (unless it's in Core theory which I haven't taken). If somebody can speak to the quality of these courses, I'd be for it. Also, do we know how long these classes will be supported and free?

That said, would that mean getting rid of HtDP? I personally think those two course are great and haven't seen any other class like it.

Could you layout a template (class listing) of your proposal using the Princeton classes for both intro and algo/theory so I can understand it better?

Also, the OpenDSA looks like it just teaches data structures. Is that true?

So

Intro
[Class 1]
[Class etc...]

Core Programming
[Class 1]
[Class 2]
[Class 3]
[Class etc...]

Core Theory
[Class 1]
[Class 2]
[Class 3]
[Class etc...]

@spamegg1

It sounds like you've both taken the Software Construction courses that were previously in the curriculum @spamegg1 and @aryzach. Can you comment on how helpful it was or wasn't to learn Java and design from the perspective of a continuation from HtDP as opposed to learning it from scratch like in CS 61B?

Software Construction doesn't teach Java from scratch. It gives you small to mid-sized project codes already written. So you don't have to know too much Java. It begins by asking you to draw UML Class diagrams of the code they give you. Then goes through how to use the debugger in IntelliJ IDEA. It teaches some Java concepts. So the entire course is more like self-study with paper and pencil; there is no auto-grader to submit programs for correctness or anything like that.

For the Final Exam/Project you write just a tiny bit of code into a large project they give you. Throughout the entire course you write almost no code. The little code you write does not solve any problems or implement any algorithms; it is about bureaucracy and bookkeeping: keeping track of class hierarchy and calling the right method of the right class at the right time. (Also they want you to pay to have your final "graded".)

I would say SoftCons is 100% design oriented. Not 99%, but 100%.

I would say it had NOTHING to do with "a continuation from HtDP". In those courses you wrote code from scratch usually. Also that course used Racket which is a functional, Lisp-like language. These two courses are so orthogonal and opposed to each other, I cannot think of anything else like that. I think that's actually what they were going for. To 'cover all bases' in some sense. I found HtDP incredibly useful, and SoftCons to be just a nuisance to go through and get it over with as quickly as possible.

I don't know about CS 61B, but when I learned Java way back in 2002, it was much, much, much different than SoftCons. I remember going through the usual motions: Hello World program, making some Java Applet GUIs (they were all the rage on the web back then), implementing a Poker game by creating Deck and Hand objects/classes etc.

So if the suggested Princeton courses are going to use Java, it will be for problem solving and not for design. I don't think there will be some complicated Java class hierarchy to write a Breadth First Search algorithm or QuickSort, you know? SoftCons would be utterly useless to prepare for those. I am guessing the Princeton classes will use Java's built-in data types like HashMap, Array and such. SoftCons NEVER goes over those.

@ola-sk

@ola-sk I've taken a somewhat closer look at 6.006.

Pros:

Covers the necessary DSA material
People seem to like it
Covers the Halting Problem
Doesn't require knowledge of Java

Cons:

Prerequisites: A firm grasp of Python and a solid background in discrete mathematics are necessary prerequisites to this course. You are expected to have mastered the material presented in 6.01 Introduction to EECS I and 6.042J Mathematics for Computer Science.
Uses Python 2.7, which was discontinued in January
Doesn't teach Object-Oriented Programming

@spamegg1

@spamegg1 I didn't explain myself well. I was thinking as if Software Construction actually teaches Java, which it doesn't really. Thus, I was asking a bad question. I was asking in order to see how much benefit there might be in using WPI's CS 2102 though), not in bringing back Software Construction. CS 2102 follows from CS 1101, which uses HtDP and How to Code videos. It actually transitions from Racket to Java, showing how the HtDP principles apply in Object Oriented Programming.

@Alaharon123

@Alaharon123

It actually transitions from Racket to Java, showing how the HtDP principles apply in Object Oriented Programming.

Oooooh, that's actually pretty cool.

I really liked those principles. Data structures determining the "template" for any functions you write, and the orthogonality of data design and function design (separation of concerns, or "aspect oriented programming"). I really wanted those principles to be continued but I never saw them again in future courses.

I think I understand your question now. Since the curriculum already has How to Code, I think I can get behind this course you mentioned. It could come right after the two How to Codes, before PLA-B-C.

@spamegg1

So I PMd @spamegg1 on Gitter since they're almost finished OSSU and gave them a pdf of just the parts of cs2013 that should be covered in Intro CS, How to Code, this potential Data Structures course, and Core Theory/Stanford Algorithms (and Programming Languages since we rely on that for OOP). Turns out if you add CS50 and nand2tetris to the mix, you get close to full coverage already with the missing parts being too scattered to have one course cover. To give the short version before I give their breakdown, Stanford Algorithms covers more than I or OP thought, Programming Languages Part C does indeed have sufficient coverage of Object-Oriented Programming although spamegg1 thinks that we should still be trying to get actual Java coverage into the curriculum, and 6.00.1x, CS50, and nand2tetris along with other courses fill the majority of Software Development Fundamentals. Here's the pdf I gave them if you want to go through it yourself without all the bloat of the full cs2013 document: cs2013-selection.pdf. And here's their breakdown, with cs2013 lecture hours added in brackets, light editing for clarity/consistency, and split up into things in Core CS and things not in Core CS:

AL/Basic Analysis [4 hours]: All covered by Core Theory (the first course)
AL/Algorithmic Strategies [6 hours]: All covered by Core Theory (it's kinda split between first, second and third courses)
AL/Fundamental Data Structures and Algorithms [12 hours]: All covered by Core Theory (second and third courses)
AL/Basic Automata Computability and Complexity Core Tier 2: the last two two bullet points (P vs NP) [2 hours] are covered by Core Theory (the fourth course).
PL/Object Oriented Programming [10 hours]: All covered by Programming Languages, Part C (PLC).
SDF/Algorithms and Design, Topics: the first 3 bullet points [7 hours] are covered by Core Theory.
SDF/Fundamental Programming Concepts, Topics [10 hours]: covered by... a lot of courses all over the place.
SDF/Fundamental Data Structures, Topics [12 hours]: covered by Core Theory, CS50, MIT 6.00.1x, Nand2Tetris

Not in Core CS:

AL/Basic Automata Computability and Complexity
- Core Tier 1 [3 hours]: not covered by Core Theory, but it's covered by the Compilers course in Advanced Programming.
- Core Tier 2: first bullet point (context free grammars) [1 hour] is covered by Learn Prolog Now! and the Compilers course.
CN/Intro to Modeling and Simulation, Topics [1 hour]: not covered by anything.
PL/Event-Driven and Reactive Programming, Topics [2 hours]: not covered by anything. However, spamegg did not take Software Engineering: Introduction and Capstone because of the paywall. [Note: I included this only because I didn't think it's covered by PLC, not because it should be covered in a CS2 course]
SDF/Algorithms and Design, Topics: The last bullet point (Fundamental design concepts and principles) [4 hours] WERE covered by Software Construction 1 and 2. They are still covered by Software Architecture and Design in Advanced Programming.
SDF/Development Methods, Topics [10 hours]: covered by Software Debugging and Software Testing in Advanced Programming.

The knowledge units not covered are a scattered bunch rather than cohesive so I would conclude that we are not in need of a course to fill the Data Structures/CS2 gap because that gap is already pretty much filled by Intro CS, Core Theory, the first half of CS50, and Nand2Tetris.

I want to note that if CS2013's breakdown of Princeton's intro course (page 448) is to be believed then switching to that would provide 2 more hours of coverage of AL/Basic Automata Computability and Complexity, Core Tier 1 (finite state machines and regular expressions), the 1 hour of coverage of CN/Intro to Modeling and Simulation, some coverage of SDF/Algorithms and Design: Fundamental design concepts and principles, and 3 hours of coverage of SDF/Development Methods. I am not necessarily advocating for it because I don't know that it's the best fit for OSSU because of the reasons stated by @kishvanchee at #664 (comment), but it could be worth considering, especially if we ever go wildcard on Intro CS. Basically I'm putting this here so if anyone ever does want to make a case for it, they can hopefully find this and use it in their case.

And maybe there's a case for moving Software Debugging and Software Testing to Core Programming? I don't know. The actual gap would seem to be Development Methods and Algorithms and Design: Fundamental design concepts and principles so maybe.

EDIT: CS 2102 would seem to be a pretty good fit for that, but I looked at what WPI students have to say and they don't like the lectures. Also, as @yeminzaw04 pointed out on Gitter, it doesn't have solutions to quizzes, labs and homework so that seems to be a no go. The HtDP approach seems to be to follow HtDP with a course teaching Java and extending the principles and teaching more about design rather than going straight to algorithms like most schools, but WPI's and UBC's courses are not great for self-learners, and Northeastern doesn't have it's course available at all. I don't remember what other schools use HtDP, but iirc from checking last time, none of them have their follow-up set up well for self-learners either.

We (me and spamegg1) encourage you to go through cs2013-selection.pdf and post your own breakdown of what's covered where and see where you may disagree.

Hey, since I remember some considerations about creating along the curriculum which has not necessarily free-only courses included, I'd be interested in opinions about how something like https://www.edx.org/micromasters/ucsandiegox-algorithms-and-data-structures goes along the rest of the curriculum if one aims at more data science related knowledge of algorithms. I've copied "what you'll learn" and "syllabus" sections from all of the courses in the micromasters for a quick comparison here. Thank you in advance.

is this the same as coursera https://www.coursera.org/specializations/data-structures-algorithms

I have now read the whole thread. There wasn't a continued discussion or interest expressed for the UCSD data structures course (part of the micromasters program). In my (amateur) viewpoint, this course seems like a good one. Can the experts here look at this more closely?

Secondly, why is Steven Skiena's book and/or video lectures not being considered? This is the recommended material for teachyourselfcs.com, but it is not even in the radar of ossu. Why is that?

6.006

I have sampled three courses on Algorithms so far

Roughgarden's course on Coursera
Sedgewick course on EdX, and
MIT 6.006 on OCW.

Among all three, I think MIT 6.006 should be the recommended curriculum here at OSSU. It seems to strike the right balance between hard theory & proof-oriented material and just implementing code.

6.006 piques the student's interest with easy to understand problems. Also, personally I find MITT 6.006 professor's narrative/style easier to follow and more engaging than either Stanford's or Princeton's courses.

Can the moderators look into MIT 6.006 for algorithms?

@krishnakumarg1984

@krishnakumarg1984, these are good resources for algorithms. Thanks for bringing them to light.

Skiena's course would appear at first glance to be a follow-up course to something like the Stanford course we currently use and only has assignments available in the nonfree textbook and is in general not really set up for free self-learning. I wouldn't expect it to be a good fit for OSSU, but perhaps a more thorough review would show how it would fit well.

The UCSD and MIT courses look plausible. I can imagine a future RFC that successfully argues for their inclusion.

I would like to offer my conclusion from the exploration of this topic over the Spring: the Stanford course is adequate and a better choice for OSSU than the Princeton course although there are knowledge areas that are not completely covered. As a result, I'm not gonna make an RFC myself. There's room to though if someone else is willing to do the work showing that whatever course is a better fit for OSSU than the Stanford course we currently use. I expect this thread will be useful in any such endeavor.

I'm glad that so many students were able to dig in and explore this question.

Students who are interested in comparing new course suggestions are welcome to find like-minded contributors in the computer science channel of our Discord. Reach out to a moderator of Discord if you'd like a dedicated channel for that discussion and exploration. And if/when there is a proposal for changing the curriculum (which would include a comparison against our curricular standards), please open a new Issue with a Request for Comments!

@Alaharon123

@Alaharon123 Will a future RFC refer to this closed issue? What are the outcomes of the detailed discussion that took place here.

It shall be helpful if the moderators can provide closing comments summarising the discussions & the decisions taken.

Here is another interesting specialization on data structures and algorithms: https://www.coursera.org/specializations/data-structures-algorithms#courses

The instructors are very good, I did their intro to discrete math course.

Navigation Menu

Repository navigation

Flesh Out Data Structures & Algorithms #664

11 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Flesh Out Data Structures & Algorithms #664

Description

Activity

waciumawanjohi commented on Mar 4, 2020

Alaharon123 commented on Mar 4, 2020

Alaharon123 commented on Mar 25, 2020

aryzach commented on Mar 25, 2020

ola-sk commented on Mar 28, 2020

m4salah commented on Mar 28, 2020

Alaharon123 commented on Mar 29, 2020

m4salah commented on Mar 29, 2020

ola-sk commented on Mar 29, 2020

Alaharon123 commented on Apr 3, 2020

Alaharon123 commented on Apr 3, 2020

kishvanchee commented on Apr 4, 2020

Alaharon123 commented on Apr 4, 2020

11 remaining items

aryzach commented on Apr 6, 2020

spamegg1 commented on Apr 6, 2020

Alaharon123 commented on Apr 6, 2020

Alaharon123 commented on Apr 6, 2020

spamegg1 commented on Apr 6, 2020

Alaharon123 commented on Apr 20, 2020

ahmadelzohairy commented on Jun 13, 2020

krishnakumarg1984 commented on Aug 12, 2020

krishnakumarg1984 commented on Aug 31, 2020

Alaharon123 commented on Sep 3, 2020

Alaharon123 commented on Sep 3, 2020

waciumawanjohi commented on Sep 3, 2020

krishnakumarg1984 commented on Sep 17, 2020

riceeatingmachine commented on Aug 21, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions