The Glade 4.0

I'm starting the Computer Science Master's program at University of Texas in January. First 2 classes:

Advanced Computer Architecture
Design and Analysis of Algorithms

What have I gotten myself into?

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

A world of hurt.

On the plus side, welcome & congratulations! Grad school was great, and at the same time I've never been so happy to be done with anything in my life.

_________________
Darksiege: You are not a god damned vulcan homie.

Congrats, homes.

_________________
The Dude abides.

Oh man. Have fun!

_________________

Congrats and good luck

_________________
"Said I never had much use for one, never said I didn't know how to use one!"~ Matthew Quigley

"nothing like a little meow in bed at night" ~ Bruskey

"I gotta float my stick same as you" Hondo Lane

"Fill your hand you son of a *****!"

Sounds horribly dull to me but you won't get shot at. Good luck sir.

_________________
Raell Kromwell

Was your undergrad in CS? Because otherwise tossing you straight into 6363 seems, um ... ill-advised. Can't speak for the Computer Architecture course. Is that 6304? I'm not doing the Systems Track and I'm avoiding the only prof that teaches it, so.... Might be okay if it's just a rehash of the undergrad version. The course will be easier if you know some assembly (on any platform) before-hand.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

Well, no, my undergrad wasn't in CS and I've never had linear algebra or C++ programming, aside from being self-taught to a minimal level. I did take the precaution of taking a couple courses at the local community college beforehand so I had a basic programming refresher, but for example...

We had an assignment to write a C++ program for a bubble sort and a merge sort of groups of random integers, up to a maximum size of 4,000,000 of them, with the merge-sort being recursive.

I had to learn how to create dynamic arrays on the fly to do the assignment; before that I only knew how to declare fixed arrays (although I suspected a dynamic array existed).

I'm just glad it wasn't in some language I never even messed with.

It took me about 12 hours just to do that one problem on Sunday, but I did complete the assignment.

The architecture class is not all that bad.

So far I'm hanging in there, but it is definitely testing the limits of my prior technical knowledge. I can't complain I'm not learning anything, though!

Oh also, these classes seem to be crossovers, where the same class is a senior level class for undergrads, but is also a core class for grad students. They both have 4000 and 6000 series course numbers.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

I'm just shocked that they're letting you take 6363 at all:



I've been around this block before, and there's not a force in heaven or hell that will make them yield a millimeter on course prerequisites. Many have tried and failed, slain by the ancient power word "accreditation". CS5303 and CS5330 are the sole consideration, and they're pretty reluctant to do even that. You have to have prior credit for the rest of those courses to get into CS6363. I'm not sure how or why it got this way, but the advising office is staight-up legit paranoid about this issue. And as far as I can tell, it's a matter of UT-system-wide policy, not just UTD.



That'd be for the undergraduate fast-track program. You have to pass certain GPA hurdles regarding a list of about 6 key undergrad courses to qualify, but if you do, you can dual-credit by taking the graduate level version of a course in place of its upper division undergraduate version. You'll also be automatically accepted into the masters program when you complete your bachelor's as long as you maintain the undergraduate and graduate GPA requirements while you fast-track. This is the only other way I know of to get prerequisites "bent". If you are a fast-track student, some undergraduate CS courses can satisfy a corresponding graduate level prerequisite. Ex: CS3305 (Discrete Mathematics II) can meet the CS 5333 (Discrete Structures) prereq for CS6363. Oh, and fast-track students can also take graduate courses strictly for graduate credit if they just need to fill out their schedule and don't have anything available for dual credit at the moment.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

I... don't know what to tell you? I just emailed the department head, asked him to unlock the two courses (they were both on the mandatory list for CS master's) he did it, and I signed up.



I see.

Kind of alarming to be reading this now; no one has said word one about prereqs or anything like that up until now.

I'm also astounded at how many of these kids walk in late, and not just a minute or two late. I mean 30, 45, 60 minutes late. WTF is that ****?

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

Huh. I...don't know what to make of that either. I don't suppose you're doing the SFS program, or something of a similar nature? There might be some loopholes for that.



Well, if your advisor signed off on it, I'd file it firmly under "Problems, Not Mine". I *am* surprised that they don't make a big hoopla about it, though. On the first day of every course I've taken for undergrad and masters, they've always passed around prerequisite forms for everyone to fill out and sign. I've always found it a little silly, but for whatever reason they seem to take it really seriously here. Maybe UT Austin is different, but I was under the impression that this was just generally a UT system thing. UTD is always chasing UT Austin's CS program, so if anything, I figured they'd be stricter about that sort of thing.



I haven't really noticed that all too much, but what blows my mind is people constantly talking during the lectures. A whispered, "hey, did you catch the last part of what he just said?" is one thing, but I mean just full-on conversation.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

Nope, nothing like that although I'm hoping that, assuming I survive this, I can get a job with the Navy on the Aegis program or something with missile defense.



I've never heard of a prerequisite form before. This guy barely passed out a syllabus; it didn't include any sort of schedule for the class or even when the midterm is. I don't know that UTRGV is that interested in keeping up with other branches of the system. The whole place is very tailored to the needs of the Valley and it only changed over from the UT Pan Am a few years ago. At that time it became, in some manner, more fully a part of the UT system although I don't know much about how that all worked.

I get to hear about how things work there - or did - because I got talked into this program by one of the professors in the CS department, who was on my church's council with me. Her husband used to be the head of the department as well, but no sooner did I get accepted than they retired. So, now she comforts me once a week.

On the plus side, one of the kids next to me in the class tonight recommended a book on data structures - another class I haven't taken that the instructor thinks everyone has; I can add that to linear algebra and C++ -and said he's willing to help me out if I need it.

[/quote]

I haven't seen that, thankfully, because it would probably send me over the edge if I coukdn't hear what the professor was saying. As it is, one of the classrooms has an air conditioning vent that's like a **** jet engine and I have to be careful not to sit underneath it so I can hear. Also, not freeze.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

From entirely too many years of involvement with academia, I leave you this bit of advice: **** can get weird and go sideways really quickly.

_________________

For some reason I was thinking you were in the Austin area now. I don't know anything about UTRGV. If they've only semi-recently come under the UT system umbrella, things might be different there. UTD is really heavily pushing for that whole "tier 1 university, STEM master race" kind of thing.



Let me guess: CLRS ("Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein)? It's a good reference book, but I'm not a huge fan of it in terms of learning algorithms unless you are an abstract thinker by nature. Most people aren't; certainly I'm not. That's mostly what made advanced algorithms and graph algorithms difficult, at least for me. Add to that these truths: "there are no algorithms for devising algorithms" and "there are no algorithms for proving algorithms". Well, there are automated proving systems, but these are proof validators not proof inventors. I.e. if you can convince the Coq Proof Assistant that your algorithm satisfies proposition P, then it really does satisfy proposition P.

Anyway, complaints about CLRS aside, I don't really have a good book recommendation for learning algorithms, either. I got a lot of mileage out of YouTube, frankly. Some of the lectures and demos you'll find there are far more cogent than anything you'll get in a book or college lecture, in all honesty.



Since you've mentioned this a couple times -- I wouldn't worry about linear algebra. Like, at all. I'm not trying to talk you out of learning about (knowledge is good for the sake of knowledge, etc., etc.) but from a purely pragmatic point of view, if you know how to do basic matrix multiplication, you're probably good to go for anything you'll encounter in grad school -- maybe even including Linear Programming, if they even offer that as a separate course. We got into Linear Programming a little in the Graph Algorithms course (CS6381) because Primal/Dual algorithms have a lot of applications in that context, but even that was nothing more complicated than matrix multiplication. Other than that, the only time linear algebra has come up at all was in undergrad algorithms. The matrix chain multiplication problem is a common example for dynamic programming. I can't vouch for machine learning because I haven't taken that. I've a got a few hours left and that might be one of the things I fill in to finish.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

It's only in the last... 5 years? More or less.





The book is called Data Structures and Algorithms in C++ by Mark Weiss. All of the professor's examples are in C++. I'll keep that other one you mentioned in mind, though, for the future.



The professor has mentioned it a few times. Also, on the first homework he had this problem:



My answer was:
(I apologize if anything is unclear; the board wiped out the superscripts and subscripts that I had in the Word document)


This all was, indeed, in the unit on dynamic computing.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

To be completely honest, it looks to me like someone just wanted to dress up the master theorem with an unnecessarily convoluted example involving some arbitrary manipulation of an arbitrary mathematical object. Because God forbid we should use simple, clear, dare I say practical examples when teaching new concepts. We wouldn't want anyone to accidentally understand anything. That would be disastrous.

Ugh. Sorry. Pet peeve of mine.

The thing is, the matrix algebra in this problem is just a pointless hurdle you have to jump over just to reach the actual problem of solving the recurrence relation. This is an exercise in making you waste an inordinate amount of time grappling with the problem domain rather than the problem itself. In other words, it's straight of the Department of Making Otherwise Simple Things Complicated. I don't know why some people think that's an effective teaching method. At best, you're wasting your student's time. At worst, it's just confusing and counter-productive to learning.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

This professor seems to be very interested in his subject matter but not very interested in the class, to put it succinctly. He's not a bad guy, but it is very hard to get an idea of what he expects from the students. I did, indeed, struggle to imagine what purpose the hadamard matix actually served.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

Had the mid-term last night. It was surprisingly, not as difficult as I was afraid of. I had a decent idea of how to answer each of the 5 questions. The first three didn't take a long time to answer; one question on big-O notation with 2 equations to solve, one on the greedy algorithm, and one on the 2-3 tree and how to delete a node.

The Big-O one had this equation:

and a rather confusingly written specification afterwards of T(1)=T(2)=T(3) = 1.

I was pretty sure that if the area inside the parenthesis is sprt of n, then b = sqrt n, because sqrt n * sqrt n = n, and I took the last part to mean solve for n at 1, 2 , and 3, so I hope I was on track with that.

The last 2 were both algorithm questions; one to write an algorithm to remove duplicate from an unsorted array of integers in O(n log n) time; my idea was to merge-sort the array, and then include an if-else condition during the merge portion where if the elements of the subarrays being merged at any point were equal, to delete one of them.

The other was a set of intervals such as [3, 6], [5, 8] and a set of numbers, and to devise an algorithm that would use dynamic programming to find one array that encompassed each of the elements of the array.

This is where I was a little nervous because his example of a set of numbers was sorted, and so were his example intervals, but the wording of the problem didn't use the word sorted. I didn't really think about that until after I left; I solved the problem as if both were already sorted.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

The part about T(1)=T(2)=T(3)=1 was establishing the base case for the recurrence relation. You need it as a starting point since the relation is defined recursively. A simple example would be the fibonacci series, which you can define as the recurrence relation:



Where underscores represent subscripts. By itself, this is not a well-formed function because it expands infinitely. To prevent that, we need two base cases, typically T(0)=1 and T(1)=1. Or, more compactly: T(0)=T(1)=1.

Offhand, your merge sort solution sounds correct. That being said, it's conceptually easier to just separate the problem into two parts:

• Sort the array with any optimal algorithm (merge sort, heap sort, etc.) -- O(n log n)
• Copy the non-duplicate elements of the sorted array into a new array -- O(n)

We accomplish the latter by the same logic you used: compare each element to its predecessor, copy it only if it differs. The first element is copied unconditionally.

Since O(n log n) + O(n) = O(n log n), this gives you the same result, but will probably yield simpler, easier to read code. It's generally best to avoid doing more than one task in a single loop or single recursive function unless it's algorithmically necessary. That's mostly a readability/maintainability thing, but it can result in more performant code. "Tighter" loops tend to have better locality of reference and therefore less cache misses.

Of course, this is uses O(n) additional memory, but that's going to be the case if you use any non in-place sorting algorithm (vanilla merge sort isn't). And just off the top of my head, I suspect that this problem can't be solved in O(n log n) with O(1) extra memory.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

See, that is the part where lack of previous courses hurt; he has not discussed base cases at all and I had never seen that notation until the test.



I kind of did that - created a new array with the sorted, duplicate-free result. As far as the code, in this particular case it was hand-written in pencil pseudo-code (my hand was killing me afterwards from the erasing) but I see what you mean for future reference.

He has discussed loops in relation to cache access, in particular with regard to nested loops, in the other class I'm taking, but it has not come up in this class. However, it's kind of a nice coincidence that I'm taking both at the same time because I've frequently seen things in one class where I can see how it applies to the other.



I don't believe so. There has been very little mention of memory consumption in the algorithm class other than pointing out that dynamic computing solutions use more of it in order to memoize (also, spell check does not like 'memoize, it seems) the results.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

I've been trying to get to my MBA for years now. I literally started filling out the application 4 years ago, and have not found / made the time to complete it.

Does not bode well for making the time to actually complete the courses. I don't know how people do it. I have no spare time whatsoever.

In the suture I'll most likely be taking one course a semester. Two at once was my original plan to be done as quickly as possible but...

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

Yeah, if you'd taken undergrad Discrete I, Discrete II, and Data Structures and Algorithms, the base case + inductive case way of defining things would have been drilled into you.

On the plus side, it sounds like they aren't being quite as aggressive with the material as the version I took. Don't get me wrong; loved the course, loved the professor, but it was a firehose. Part of that was taking it in summer session, but we pretty much had to cram your midterm material into a two day crash course review of undergrad algorithms. Either way, I don't envy you. Long story short, don't sweat it if you find the course a struggle. It's a lot to catch up on in a short time. And honestly, most graduate professors just want to see that you're grappling with the subject. As long as they can tell that you're putting in the effort, you'll probably walk away with a B at worst.


Unless you are explicitly given a memory constraint, it's safe to assume that there isn't one. You may have it thrown at you at some point to make you realize that time complexity and memory complexity are usually inversely related (classic time/memory tradeoff), and that time complexity is often not the most important factor in real life. There are lots of contexts where the O(n) memory you take for granted isn't available. "Big data" analytics, for example. How do you sort 500TB of data stored on sequential-access-only memory (ex. tape)?

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.

I hope that's the case. We got the Architecture mid-term back last night; I got a 75 on it. Initially I was horrified, but then I discovered there were a lot of grades in the lower 70s and in the 60s, and the highest grade in the class that I'm aware of was an 80. One of my classmates also said that this professor doesn't return homework because he likes to keep the curve secret; I hope that indicates he is, indeed, curving everything.

I actually would have gotten higher but I completely brain-farted the formula on the question about how to calculate CPI for accesses when Tier 2 cache and RAM are included; I wasn't that far off on the final answer but the work I wrote out was basically wrong. I did feel good about getting maximum points, though, on the question involving instructions in the delay slot during a branch because I initially didn't understand that at all and read that material 6 or 7 times trying to get it before the test. I'll get the Algorithm mid-term back on Monday; I'm feeling fairly hopeful that I'll get a similar result.



Slowly.

My goal, after I finish with this is to look for a job with the Navy or the MDA or maybe at Redstone working on missile defense. It occurred to me that when you're designing software for something that's moving at between mach 10 and mach 15 and trying to hit something moving at the same speed, efficient algorithms are probably pretty important.

_________________
"Hysterical children shrieking about right-wing anything need to go sit in the corner and be quiet while the adults are talking."

I don't know a great deal about computational geometry (and less about missile targeting), but the underlying problems may be relatively simple. For instance, we already know how to solve the closest pair problem as efficiently as theoretically possible (O(n log n)). In a lot of cases, we can solve the speed problem more pragmatically: throw more hardware at it.

The bigger challenge in those kinds of systems is formal proof. No one wants another Patriot missile failure scenario. I should hope that the powers that be now demand formal, machine-validated proofs of correctness for all code on life-critical systems. As well, these sorts of systems almost always use some flavor of RTOS. So besides being able to formally prove that the software is bug-free, you need to be able to prove the absolute worst-case time limits of your code. Edit: And just to be clear, I mean in concrete terms. I.e. "this routine will never take more than 13 microseconds to execute."

I'd also be surprised if there's not a decent amount of parallelism involved, since that's really the only other way of speeding things up that are at an algorithmic minimum. Synchronization is a notoriously difficult problem. Everyone (and I mean absolutely everyone) is bad at it. Virtually every *production* bug in every program ever written is either due to someone getting a loop invariant wrong, or incorrect synchronization.

_________________
Sail forth! steer for the deep waters only!
Reckless, O soul, exploring, I with thee, and thou with me;
For we are bound where mariner has not yet dared to go,
And we will risk the ship, ourselves and all.