Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Course on Data structures and algorithms

  1. May 15, 2005 #1
    Hi all,,

    I am just about to learn a course on Data structures and algorithms in next semester.
    Can u guys pls explain me the preoper importance of this course and how should i prepare myself to make full usage of this course and
    Lastly pls recommend some good books to me.

    I will be grateful for urs kind advices.
  2. jcsd
  3. May 15, 2005 #2
    Data Structures refers to constructs or ADTs to organize data, such as linked lists, stacks, queues, trees, hash tables, etc. The algorithms portion analyzes the complexity and other properties of algorithms, and provides proven templates for most common algorithms such as searching and sorting. A good book is "Data Abstraction and Problem Solving with C++/Java - Walls and Mirrors" from Mark Carrano and Janet Prichard.
  4. May 15, 2005 #3
    Is Java Prerequisite of this course...i mean to say that does i need to know java well to learn this course well
  5. May 15, 2005 #4
    I think wikipedia does a great job of explaining data structures in general.

    This class is critical! I used the topics in every single one of my upper division classes (except perhaps the ee ones). The topics also come up in every single program I have written as a professional. Do yourself a huge favor and learn it the first time.

    I know some universities teach this class in Java. You should email your instructor or dept to find out if yours does. But in any case, the material taught in this course is not particular to any computer language. They just need something for you to do your homework in.

    Personally, I wouldn't buy a book to prepare. I would just use wikipedia. After reading the first link use this link:
    If you understand the list, stack, and heap, then you will have a solid head start.
    If you also understand the queue, hash, tree, then you will almost be done with the course.
    The best way to make sure you understand the algorithms is to be able to implement them in your language of choice without looking.
  6. May 15, 2005 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This course should teach you the basic building blocks for doing many programming tasks efficiently, and give you a foundation on how to design structures and algorithms for more complicated tasks.

    For example, one algorithmic step I often see from non-computer science people is:

    "Now sort the stuff we found so that when we get new things, we can use a binary search to tell efficiently if the new thing is in the stuff we already found".

    But you can shave an order of magnitude off of the running time if you instead use the step:

    "Now put the stuff we found into a hashtable so that when we get new things, we can efficiently look it up to tell if we've already seen it"
  7. May 15, 2005 #6
    you do not need java in the course(unless specifically the teacher requires it)
    the course is a theoretical course in designing structures to manipulate data.

    Take an classification example from the realworld(Ie pop machines, phone books, game engines)
    Arrays -Popmachines
    Stacks - plates
    Queues - Queues
    Linkslists- Phonebooks
    Trees - BSP spatial partioning ttrees
    Graphs - Airport grid system.
    the list goes on.

    I suggest getting the "GOD" book on the subject by Sedgewick "Algorithms In C++ Parts 1-4: Fundamentals Data Structure Sorting Searching" (he's got a version in C to if thats your prefered style...i prefer the C...he also has the book in Pascal)
  8. May 15, 2005 #7
    Sedgewick has a Java version too along with a couple of more basic intro books. Give Amazon or your local book store a peep.

    Along the lines of egsmith's comments though, I wouldn't bother buying a book before you take the class---unless you know what book will be used for the class. Read what you can on the net and then, this is the key BTW, start playing around. Make some records and manipulate them. Make some link-lists and manipulate them. Just play around with the basics of structures. When you write your code, do things like print the memory locations of each variable if you can and watch how these do or don't change.

    If your IDE/compiler allows for stepping through a program then do that and take note of how your system is effected(I use x-code so I can't speak for other compilers/IDEs). If you are using a command line compiler then add breakpoints to your code at key points. Watching what goes on is much more informative than being told what to expect from a professor.

    I think learning a computer language is 100x harder than learning math. A computer language is a language. You have to communicate with a uP and coax it to do exactly what you want it to do. That takes practice. The best thing for you to do between now and your first day of class is to practice.

    My 2 cents.
  9. May 16, 2005 #8
    Thx Guys.....I will like to try in this way...urs suggestions are very useful.
  10. May 16, 2005 #9
    ITs "Cormen" being followed by the instructor here...how is this book?
  11. May 16, 2005 #10
    Algorithms and Data Structures is two-thirds of what real "CS" is all about. The other third is Languages. These three concepts form the bedrock of Computer Science.
  12. May 17, 2005 #11
    Introduction to Algorithms by Cormen, et al. is an excellent book. It's over 1000 pages and weighs a ton though. It comes in very handy for other courses like computational complexity and computability. The book uses pseudocode, which I prefer over C++ or Java because it illustrates the concept without any unnecessary code.
  13. May 17, 2005 #12
    Data Structures & Algorithms is not the same as Programming (say, programming techniques, structured and OOP, Software Engineering, etc.) but rather a subset. Though it is categorized as crucial to Computer Science, there are two factors that are making this subject more marginal. First, the extensive APIs provided with compilers, or even with languages themselves, are including ready-made data structures. Second, with the improvement of hardware, the Algorithms portion is also losing its importance about writing efficient code.
  14. May 17, 2005 #13
    You can't be serious. One can easily make the fastest available computer perform lousy with poor algorithm selection. See Hurkyl's post for an example. I do agree that because of the availability of libraries and what not you don't need to write your own implementation of quicksort or whatever, but understanding the algorithms and when/how to select them is, and will remain, critical to computer science.

    Also, hardware is getting faster but data set sizes are not shrinking or staying constant...
    Last edited: May 17, 2005
  15. May 17, 2005 #14


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And don't forget the abstraction penalty! The power of hardware is often leveraged to make generic tools effective (when they would otherwise be ridiculously slow).

    This applies not only to libraries and code design, but even to the choice of language! It's what makes interpreted languages such as Python (and even Java, in its first incarnations) viable.
  16. May 17, 2005 #15


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    And frankly, I can't remember the last time I used a piece of software without being annoyed by delays in doing things.

    (Excepting those old DOS games that were carefully tuned to run at the right speed on a 8 MHz processor!)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook