In this thread we discuss our progress reading “Introduction to Algorithms, Fourth Edition”.
We gather every Saturday and Sunday at 12:00 (noon) UTC.
I have made the decision to stop posting a schedule because few people have ended up following it - you should read as much as is appropriate for you on any given week and do as many exercises as you can. Gathering in this thread and talking about our progress is still beneficial.
The user who said we were going too fast was definitely right, I've only just started chapter 3 this morning. It's been good though! I'm flying abroad next weekend so I'll take a break from algorithms because I don't want to carry my big hardcover exercise/note book.
Also I've implemented binary search in one of my side projects! I've written a Twitter bot, and I used it to determine the highest allowed resolution I can compress an image while still staying under the 5MB limit for uploaded photos. Does that make sense?
bbumpp
how can I avoid (O)n^2 runninig time in my searches?
Linear search is linear-time by definition and I don't see why yours is quadratic
def linearsearch(lst, elt):
for (i, v) in enumerate(lst):
if v == elt: return i
linearsearch([1,2,3,4,5], 3) # 2
linearsearch([1,2,3,4,5], 8) # None
Perhaps it would be easier if you would write what you are even trying to do, dumbass.
any help?
cmon user
>CLRS
lmao brainlets, pic related is much better intro to algorithms
Have you read it?
help
that table is retarded
i'm new and retarded. Are all data structures actually implemented only using arrays or pointers/lists? If so, are more complex data structures are just built up upon the basic ones like stack/queue/dictionary?
>Are all data structures actually implemented only using arrays or pointers/lists?
You can implement a bunch of stuff with arrays and pointers, but you don't necessarily have to do it that way. You can use whatever abstraction your favorite programming language offers. For example, if your programming language does not offers pointers you can implement them with an array, and vice versa.
>If so, are more complex data structures are just built up upon the basic ones like stack/queue/dictionary?
Complex data structures are usually a variant of the very general fundamental ones, pretty much like trees are graphs with specific properties.
Compute the inverse function of each of them and plug in the numbers.
GROOMER ALERT
Everything's just pointer arithmetic and registers.
A dictionary is a hash table full of dynamic arrays. A hash table can be as simple as just an array of pointers, but it's really not about the array it's about the hashing mechanism. That's what makes a hash table a hash table.
While there is a set of building blocks that if you understand it can get you there for 95% of use cases, I'd go further than just "pointers and lists." I'd say the building blocks are Hash Dictionaries, Sorted Lists, Dynamic-sized Arrays and Sparse Arrays, Queue/Heaps/other linear linked list variants, Trees/Graphs. Probably missing a few, but you can get far just with those concepts.
Could you show me how you did it? im having trouble learning how to implement these data structures in actual code but I understand what they are.
which data structures are you trying to implement? I only implemented binary search and recursive insertion sort to test them and see if my algos were correct
>Are all data structures actually implemented only using contiguous chunks of memory or noncontiguous chunks of memory hooked to each other?
yes
well, any of them but since you did binary search that would be good.
Can you explain what difficulties you're having? I can't remember if they gave us the pseudocode for binary search or if that was an exercise...
Dont see why a search would be quadratic, at most you should only have to iterate through the data set once
did you mean sorting?