Question for CS majors

College Majors Engineering Majors
1

<p>I know there are many on College Confidential, so I'll ask here.</p>

<p>Some background:</p>

<ol>
<li><p>I'm in the CS program in my school (University of Washington, they have a competitive CS program, being next to Microsoft and all, I think ranked #6)</p></li>
<li><p>I'm also a math major. And I enjoy problem solving and logic in general. I do well in Physics as well.</p></li>
<li><p>I had no programming or CS experience prior to the UW. Where I took 2 programming classes (Java classes), they were challenging imo, though they were meant to be, to weed out many kids who just weren't cut for the CS major at UW.</p></li>
</ol>

<p>Well I'm starting the upper-division classes in the CS major starting next quarter since I just got into the CS major. It's been about a year since I took those 2, and only 2, programming classes. And I realize I don't remember much. How important is to know and master the stuff we learned in the 1st 2 programming classes, as we take the upper-division courses? Here is what hte 1st 2 programming classes covered</p>

<p>CSE 142 Computer Programming I (4)
Basic programming-in-the-small abilities and concepts including procedural programming (methods, parameters, return values) , basic control structures (sequence, if/else, for loop, while loop), file processing, arrays and an introduction to defining objects. Offered: AWSpS.</p>

<p>CSE 143 Computer Programming II
Continuation of 142. Concepts of data abstraction and encapsulation including stacks, queues, linked lists, binary trees, recursion, instruction to complexity and use of predefined collection classes. Prerequisite: CSE 142. Offered: AWSpS. </p>

<p>So I think I'm already in a disadvantage because I haven't been programming for long, while most the kids here have been programming for a while. Nonetheless, I'm a math major and enjoy problem-solving and logic in general.</p>

<p>But I'm just curious, how often do you use the things we learned in those classes in the upper-division courses. I mean, if looks, for loops, while loops, and all the logic control algorithms I still remember well. But binary trees? linked lists? recursion? arrays? Will they come up a lot?</p>

2

<p>Constantly. Those are some of the basic foundations of computer software. As you move up, you’ll look at much more complex data structures and algorithms as well.</p>

<p>Think of it this way: the control structures you mentioned (loops, if, recursion) are like the alphabet and common data structures (like binary trees and linked lists) are like words of a simple vocabulary. Later on, you’ll learn how real sentences are put together.</p>

3

<p>If you’re good at problem solving (math and physics) then CS should be no problem for you. You’re not at a disadvantage, you may even be at an advantage (since you have the chance to learn things the right way the first time and build good habits, not always true of self-learned programmers).</p>

<p>Besides, probably the most that people at your level now know don’t go past sophomore class levels in CS.</p>

4

<p>Interesting…well next quarter I’m talking a class that looks more mathematical and theory than the programming classes I’ve taken. So I won’t need to brush up my programming before I take this class.</p>

<p>CSE 311 Foundations of Computing I (4) QSR
Examines fundamentals of logic, set theory, induction, and algebraic structures with applications to computing; finite state machines; and limits of computability</p>

<p>But I guess, for future programming classes, knowing binary trees, recursion, and linked lists are essential?</p>

5

<p>Binary trees, recursion, and linked lists are among the <em>most important and fundamental</em> things every CS major knows. I would be surprised if at least one wasn’t brought up every session of every CS course you take in college… that may be hyperbole, but not as much as you might think.</p>

<p>I mean, recursion will come up in your theory class next semester. I’d be surprised if you didn’t cover binary trees as well. Linked lists may not get extensive coverage. But you’ll probably talk about graphs.</p>

<p>It’s curious to think that you, a math major, doesn’t feel comfortable with structures and recursion, when these are arguably more mathematical than, say, iteration (“loops”).</p>

6

<p>

</p>

<p>QFT. You should definitely have a good handle on the most common data structures and algorithms that are taught in your intro courses. They will, without a doubt, come up later.</p>

7

<p>AMT</p>

<p>Wow I can’t believe they would be so important. They seemed to me just one of the many different type of structures we will learn and can use. For a Physics analogy, it’s like learning about friction. It’s a force, you go over extensively, but it’s just one of the many type of forces you learn and you will not need to know the details about friction in every Physics course you take in the future. Sure many times you will, but it’s just one of those things that you will need to know when you need to know it, if that makes sense. But I guess not…</p>

<p>About your math major comment, I as of right now don’t see how it has a lot to do with math. I know it’s been said a lot how much computer science and math overlap, but I don’t see much right now. Computer science to me has more been about logic and problem solving. Thinking logically through a given task and solving it. Math has a lot of logic & problem solving too true…but Computer science seems to be purely based on logic. Iteration seems to me the most logical approach in most problems. I’m just not that comfortable with the recursive type of thinking, and binary trees, etc. Maybe it’s because I have programmed for 5 months all my life (and that was a year ago). </p>

<p>But thanks for the advice. Just a quick question. Do you suggest I get comfortable with recursion and binary trees right away? Because as of right now, I’ll say I’m not very comfortable with them. Or do you suggest, when they come up, review everything you learned quickly, and the upper-division classes will help you master recursion/binary trees with whatever they make you do. </p>

<p>So basically, get comfortable BEFORE they come up again, or learn them again as they teach you again, and everything will just automatically start making more sense as you work more problems with them.</p>

8

<p>Your university should have some core course (usually second year) called “Data Structures and Algorithms” or something similar. </p>

<p>Typically it is taken immediately after the basic programming courses. Depending on the school, the course may be entirely theoretical (no programming, only paper based pesudo-code and analysis as it was in my case) or a split between theory and implementation assignments (usually C or Java).</p>

<p>This course will explain all the basic stuff you need to know about data structures in a rigorous fashion. Try to find some old outlines to get an idea of what’s covered.</p>

<p>The textbook that is usually used is Introduction to Algorithms from MIT (known as “CLRS” by its authors’ initials). I’ve also seen “Algorithm Design” by Tardos and Kleinberg as well. You will surely find CLRS in your library if you’re curious.</p>

9

<p>I would suggest you get acquainted with trees and recursion pretty damn quickly. They’re so basic that no class is going to wait for you to get “comfortable” with them. Hell, every single interview I’ve had for a CS job involved some tree (many different kinds of trees) question, and recursion was the basis of many of my answers.</p>

10

<p>“Wow I can’t believe they would be so important. They seemed to me just one of the many different type of structures we will learn and can use. For a Physics analogy, it’s like learning about friction. It’s a force, you go over extensively, but it’s just one of the many type of forces you learn and you will not need to know the details about friction in every Physics course you take in the future. Sure many times you will, but it’s just one of those things that you will need to know when you need to know it, if that makes sense. But I guess not…”</p>

<ul>
<li>I guess this is a fair way to feel. There are certainly aspects of CS that you don’t need to know intimately to do well… for instance, there are algorithms the details of some of which are not necessarily important. Operations on some data structures may not need to be known in intimate detail. etc.</li>
</ul>

<p>In Physics, you can identify a few of the most used and useful concepts every undergraduate major will learn about: force, momentum, potential and kinetic energies, electric and magnetic fields, etc. There are certain methods - Fourier transforms, fourth order Runge Kutta integration, etc. that are used to solve real problems. Certain truths about these things - conservation of angular momentum, convergence of series, etc. - are required for it to make sense.</p>

<p>Binary trees form the basis for an extremely important search algorithm, and searching is one of the two most basic (and therefore, in a sense, most important) problems in CS. Trees are important for the study of programming languages, operating systems, etc.</p>

<p>Recursion is an important practical tool, and as far as theory is concerned, it is of paramount importance. A comparative look at programming languages necessitates familiarity with recursion, as anyone who has used functional or logic languages can tell you.</p>

<p>Linked lists… well, I would say they’re at least as important as arrays, and arrays are pretty important. There’s a lot of cool stuff you can do with them, like resizing and inserting, etc.</p>

<p>These three topics are at least as important to CS as force, momentum, and energy are to physics, and are also at least as basic. There’s a lot of more complicated stuff for which you can forget the details, but I don’t think these are strong candidates.</p>

11

<p>"But binary trees? linked lists? recursion? arrays? Will they come up a lot? "</p>

<p>Like it was pointed out earlier, binary trees, linked lists, recursion and arrays are some of the most important concepts in CS and the merging of Math & CS. These concepts are also mathematical.</p>

<p>If you end up taking Combinatorics (the official course…not that Discrete Structures course), you should dive into “generating functions” which relates to recursion. There will also be some recursion in a Theory of Computation/Automata course and more in a Computational Complexity course…all which could be given by the CS or Math departments (and possibly both at some schools).</p>

<p>The more you get into C/C++, the more you will get into pointers and linked-lists.</p>

<p>Arrays?..Think of matrices and that leads to Linear Algebra, especially when doing computations.</p>

<p>The answer?..all of them will be used a lot.</p>