In this thread we discuss our progress reading “Introduction to Algorithms, Fourth Edition”. We gather every Saturday and Sunday at 12:00 (noon) UTC.
Reading goals for next Saturday: Chapter 3
I've extended the time we have to finish chapter 3 because I was pretty busy with work this week. Did you get through all of this week's content? Let us know if you think we are going too fast or too slowly.
Today's discussion questions: Name a loop invariant property which is not mentioned in the book, and prove that it is loop invariant. 2.1-4 Write pseudocode for linear search, which scans through the array from beginning to end, looking for x . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfils the three necessary properties.
You will gain the most by doing the exercises and problems yourself! Spoilers are not enabled on this board, so please not post solutions for exercises or problems for sections: 3.1 and beyond
Notable changes from the third edition for this week’s content: None
> 2.1-4 Write pseudocode for linear search, which scans through the array from beginning to end, looking for x . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfils the three necessary properties.
My solution:
for i=1 to n if A[i]=x return i return NIL
Loop invariant: At the beginning of every iteration, no element of the subarray A[1:i-1] (or if i=1, the empty array) is equal to x
Charles Fisher
jeeze this one has a new version too? AIMA got a new edition in the last year or two too (which I have still not gotten around to).
CLRS is too dry for me to read back-to-back, but I could manage it with AIMA.
Should I but the printed one? I use my iPad to read and solve the CLRS, but it seems everyone else is using a printed actual textbook.
Mason Thompson
I'm using a PDF copy for now, and I'm going to buy a Kindle in a few days when they're on sale for prime day. I personally wouldn't buy a paper copy, I'd only borrow it if my university had the fourth edition.
Lucas Barnes
this_book = "A Common Sense Guide to Data Structures and Algorithms"
I started reading $this_book, done with chapter 10, and solved many example problems in code. Don't have any experience with leetcode and I think I'm average at coding (so far) What other resources should I use before starting with leetcode? My classmates keep posting solutions to problems like width of a binary tree and all, I just can't understand them. I'm also struggling to pick my "main" language. I did most of my projects in C or JavaScript but they both seem a bad choice. I'm really confused. Is there a guide/resource you think can help me :(
Samuel Rivera
How do I determine non-trivial loop invariants?
Nathan Walker
determine?
Gavin Green
Determine/find
Aiden Myers
It encompasses 2 semesters worth of CS, you're expected to take a year to read it.
Jayden Cook
from what we've read so far, you just have to look for loops and figure out how the algorithm breaks down the problem I dunno, there's not a "method" for it
Joshua Nelson
that does not make it less dry
Ayden Bell
I think I'm starting to understand loop invariants now... they're less formal and more just a general statement concerning the outcome of the loop, no? What I came up with is: The subarray A[0...(i-1)] does not contain the target value (x). Pretty much the same as what you said. I think this is correct?
Carter Mitchell
you successfully FOMO'd me into reading this...i have to catch up to chapter 3 yeah... ok
Elijah Collins
Let me see if I'm really getting this... For the selection sort exercise later in the chapter, would the loop invariants be: Outer loop: The subarray A[0...(i-1)] is sorted Inner loop: min is the smallest value in the subarray A[i...j]
Owen Thompson
you can do it anone!!
>they're less formal and more just a general statement concerning the outcome of the loop, no I mean it sounds pretty formal to me, it feels a framework for proving the correctness of an algorithm through induction
Josiah Collins
Look at primal-dual theory and complemetary slackness conditions. (linear programming)
Owen Wright
Pure math.
Michael Butler
>Finally get a job >Summer break turns into summer grind I swear I'll read through CLRS some day... Maybe
