okay good morning everybody i hope er is having a wonderful day so i want to welcome you to cs 210 data structures and algorithms otherwise known as data structures and abstractions uh so my name is dr daniel page but you can just call me daniel or dan i'm i'm not too much of a formal guy with when it comes to these kind of things uh but uh my email is daniel.page at you regina dot ca uh you can always reach out to me by email i have office hours that are scheduled likewise you can reach over your courses to reach out and ask me anything i'm usually very happy and quite accessible to when it comes to asking questions over email i do have my scheduled office hours they are as i'll mention in a moment they're going to be on a couple of the days during the week so anyways what i'm going to do today with you is we're first going to talk about the course outline and then i'll start talking about some things with the remainder of the time we have here today so as you might know this is a compressed course so i must stress that we're meeting we're going to be meeting a lot more frequently than we would be in a normal fall winter term so just another to do item i want to mention is that that late and later on in the term there will be the final exam during the exam session it uses proctor track so i require you to do this onboarding quiz so i usually recommend just getting out of the way as soon as possible it's available to you to get started wherever you like but there's no hard deadline on it but i highly recommend you do it just try to get it out of the way so you don't have to worry about it later anyways let's start talking about actually before i get started i wanted to see how is everybody doing today is everybody doing great now wonderful wonderful no i'm really happy to hear that i'm really excited to be working with everybody this term i'm hoping that we'll have an exciting time we'll get to see all sorts of fun things today well today and this term but well i must stress that a lot of the things that we're going to see in this course are going to be fundamental to the study of things such as data structures algorithms you'll find a lot of this will form a nice foundation for a lot of the things that you'll see in later computer science courses so anyways let's start talking about the course outline i'm just gonna walk on over here so let me just get on over here and let me just let's see here okay let me just refresh my camera for some reason i'm mysteriously not there let's there we go there we go that that was that was uh i i can't explain that one other than it was a little bit buffering [Laughter] it was what we call the phantom professor so anyways let's start talking about the course outline here so i recommend that in your spare time whether it be after class or just if you already looked at this that's great i recommend you look through this document because it's very specific about a lot of things so i highly recommend you check out this document so as we know we're here right now so we have classes at these times so monday tuesday wednesday thursday as you might expect you'll find that the office hours information is here we'll be doing office hours over zoom so i have a link on the course website for this zoom room for example at office hours just before class so you'll find that on mondays and thursdays this is the times i've set up right now based on how other courses are scheduled this term so i'm hoping that these times will be okay with everybody um or at least one of the two days are so these are a perfect opportunity to say if you have a very specific question or something very specific you want to chat with me about or if there's something any kind of concern just generally i'm very happy to talk about it with during office hours like again i'm very accessible by email so just keep in mind that that i try my best to be available for students but keep in mind for office hours they're at scheduled times so when it comes to this a prereqs so to be here you have to have gone through math 110 and cs 115. the cs 115 is especially important because it sort of forms a lot of the stuff that came just before this class so i'll be picking up a lot of things that you sort of left off at in 115 and building on a lot of that another thing is that i'll expect you to have some knowledge of c plus obviously not like a master or anything we've only seen a couple of classes possibly at most on this topic or at least that but if you ever find yourself needing a good resource on c plus there's this good website called cpusplus.com has a lot of resources some of my notes will refer you to parts of this website and some other ones too course websites on your courses you're here so i assume that you found the link so anyways one thing i want to note before i get ahead of myself is that there is an optional textbook in the course it's this one by goodrich tameza and mount so it's called data structures and algorithms in c plus it's a good supplemental text but it's absolutely not required for this course so i must stress that you're not required to have a textbook in this course the course is mostly self-contained so i won't just i'll be i won't ask you to like oh and in this book read this chapter i won't do things like this instead what will happen is we'll do our lecture together during lecture time i'll we'll do notes together and sometimes i'll post examples or certain segments of the notes i'll post in there and ask you to read them so just must stress that you don't need a textbook to be successful in this course but i know that some students especially want to see more code um sometimes that's helpful for some students i know that this book this data structure is an algorithm c plus plus has such a thing and i must stress that if you have any questions i'm going to answer those as we go i've just got to look over there because i have my my chat over there i'm just going to move it on over here and just cross my fingers i get it let me just actually well i'll i'll address the questions as we come along to this so uh i know i i don't have the perfect vision to see you all the way over there um i know i see something interesting over there uh let me just just give me one moment i'm just gonna pull the chat over here just for a moment just to make this a little easier okay let me just there we go thank you i apologize for the delay okay so i'll be getting to that in one moment that that's a lovely question so i know i see something interesting there so i'll be getting to that one moment uh so the big thing with this course is i'll be introducing you to the idea of abstract data types data structures we'll see some basic computational algorithms we'll see some analysis some introductory analysis of algorithms and we'll see a lot of different kinds of data structures in this course some of them you'll explore more in the lab other ones will focus mostly here on lecture so for example this will include things like lists stacks cues recursion we'll see in this course we'll see things like basics of computation complexity sorting we'll talk more about that i know you've seen a little bit about that in 115. we'll be building on your background from that we'll see things like hashing we'll we'll probably wrap up the course with trees we'll talk a lot about these so-called trees they're a very very important collection of we can think of them as data structures especially later on we'll see how we can represent these hierarchical structures called trees and they're not like the trees you have out in the park they're not the same thing but most certainly it is something akin to this kind of structure so we'll see more of this stuff as we go along i have a list of these topics that we're going to go through roughly in the order that is given there so just to re-emphasize you don't have to get this textbook um it's not required for this course but i know that some students like to have an additional text that they can read along with everything that's going on i encourage you if you find yourself one of those kind of students i encourage you to do that it's something that it will find beneficial if you need say for example more resources for code this book has more code in it as opposed to you're going to see a lot of this class i'm going to try to introduce the idea that we can think about problem solving in a much more i don't like to use word abstract but most certainly a much more general way instead of thinking about just programming as a way and means to solve problems we'll think more about algorithms and how we can formulate data structures in a way that doesn't tether just to one programming language so you're going to find that a lot of the things we're going to see in this course are going to be beneficial say if you pick up another programming language so that being said let's actually are there any questions before we proceed i will be getting eventually to talking about assessment and all of that but yeah you'll find the list of topics here so this will be generally the the kind of order will go through things with the exception i think i i may cover stacks and cues a little earlier but we'll see we'll see okay so if there aren't any questions uh let's proceed i'm gonna talk a little bit about how the course will function so keep in mind that this is as we know a remotely delivered class so it is compressed as well so we'll be doing lectures over zoom and this is just a link as you have on the course website this is just the same details if you find yourself needing a link for the youtube channel where i'm posting these lectures afterwards these recordings of them this is a url to that but also you'll find the same thing on the course website also there's a playlist so if you find yourself just wanting to say for example to do a review after you can actually literally just go through the lectures it's it's not like you have to be like oh i have to go through my notes well you can go through your notes and you also have all these other resources too so i see it as a win-win for students so one thing i encourage you to do is the take notes during lecture i'll be doing lectures with boards out in front for most of the time so keep in mind that will be kind of an integral part of helping you learn but also engage with what we're doing but i must stress that after each class i'll be posting the lecture notes so the stuff you see me holding some papers sometimes those are going to be the lecture notes that also i'll post this is for the sake of accessibility in case there's any students have difficulties taking notes themselves also sometimes i put extra examples in there that you might find helpful and sometimes i refer you to them also i mentioned about office hours earlier i must stress that i usually put a weight room on the office hours so if there's ever a time where you have say a couple like say a couple you guys want to come on down and you want to come ask me questions just let me know that somebody else is in the waiting room that you want to come in at the same time like i said these are scheduled office hours so uh this is just because of my availability but like i said i'm usually very available over email otherwise but usually i like to be helpful for students um but yes uh typical stuff with zoom i'm pretty sure i don't have to explain a lot of these things just uh but yeah i encourage you to participate in class uh we're gonna have ourselves a wonderful time you'll find that i do a lot of demonstrations and i like to ask a lot of fun questions to keep everything kind of rolling as we're going along so otherwise of course if you don't understand something while we're doing the lecture i'll try my best to answer the question or i'll usually like to ask just to check to see how everybody's doing but if you have any questions during lecture don't hesitate to stop me whether it be your voice or you want to type in the chat i'm happy to hear from you this is one of those things that's important so this is about the assessment next uh so the course mark breakdown so they're actually only so in this course there are the labs uh uh those start next week um keep in mind that that's that's all dealt with the lab instructor so i have very hands off with the lab instructors that's something separate from me the only part that relates to me is recording your lab mark at the end so when it comes to questions about the lab i think i put a link on the course website to the labs web lab page but most certainly you'll find that most of this mitigation when it comes to the lab is done with the lab instructor so there are three assignments in the course as i mentioned this course is a compressed course so you'll be given about a couple of weeks to finish each assignment so for example the first assignment will come out on may 4th i usually recommend that you work start working on them as early as possible because especially with this first one because we'll be sort of covering the material as we go through things so so just be mindful of that you'll find that because of the compressed nature of this course normally i alternate the assignments to be like written then programming then written in programming because of the nature of this course you'll find that the first assignment's going to be a purely written assignment the second assignment will be a programming and written assignment and the third assignment will be programming so the programming language of choice in this course is c plus um so you have some familiarity with that from 1 15. and finally there is a final exam so there is no midterm examination in this course you'll find that the breakdown here is that sixty percent is allocated to the final exam and then there's the three assignments each worth ten percent and the lab is worth ten percent uh so uh that being said uh there's just a couple tips i have here about emailing me just to keep it so i make sure i can see your email very easily so so things like putting the appropriate subject line makes it a little easier for me to see what's going on assignments like i said i'll let you take a look at this in your own time but just be wary um i'll expect it to be formatted in a specific way when it comes to written parts of assignments likewise when it comes to programming make sure you follow carefully the specifications so when you see my assignments you'll see that i get very specific specifications where i'll say okay i want you to implement this this this and this and this so make sure you review those very carefully because that will tell you what i'm expecting um so you'll find that the setup of them is almost gonna be like where i give you some base files then i ask you to implement say another like a c plus plus class um with that so you'll give it given usually some files to help complete a piece of software and usually has some fun application to it that really emphasizes the importance of employing that data structure so that being said are there any questions so far as this seem okay so far so give me two thumbs up if this is okay so far oh there's a question sure what's your question [Music] okay yeah so in this course you'll find that i expect the programs have to compile to get full grades so for example if uh if for example so i'll answer your question in two parts so the first one so first let's reiterate the question it's about how exactly the assignments are being graded uh when it comes to programming because the question is okay does it have to like have a specific output or something like that what what the goal here with the programming assignments is that you're going to not just have to program it but that's some there might be i'm expecting you to have submit a program that compiles so all happen very often with these assignments is i'll give you a set of specifications and the breakdown will be like as follows that i'll expect that you and try to implement as much of it as possible obviously implement all of it uh that'll be a way to get full grades assuming it is correct um it has to compile uh the main reason why it has to compile so they can execute so you'll find that there's gonna be a blend for the marking that where a part of it is gonna be going to testing so a part of it will be testing usually it's about usually it ranges from about 40 to 50 percent is reliant on having it where it compiles and it passes some set of tests so these sets of tests these will be individual marks so you can for example pass like half the test and you can still get an okay mark but if it's a all of them you will do great i usually try to make sure that you have access to some of the testing suites that we use for the testers and i must stress that i'm not going to be overly picky about which like id you pick to implement things in c plus just be wary of very specific technical issues with using that id so for example i know i know uh replit for example can sometimes be a little lenient when it comes to uh if you don't define instance variables or attributes for a class sometimes they'll just put them in for you assuming that it has a value of zero which may not necessarily be the case uh sometimes it actually is a value that is stored in that memory spot uh so i'll usually try to remind you of these couple little things but yeah if you want to use wraplet that's okay if you want to use visual studio code that's okay i'm okay with this um just the key thing is it has to in this course you'll find that i'm gonna expect it to compile with g plus plus so the compilation process has to go through that um uh usually the tas will usually be compiling on windows typically uh so they'll be compiling g plus plus through there um so keep in mind that like i said just be mindful of the fact that sometimes replica does some convenient things for you uh so just to clarify one partial part of this so so if our output is not correct but we wrote some part of correct we'll be getting marks out of it yes so so there will be a part uh so there will be automated tests that's the best way i can describe it to you so compiles you get some marks for that it has some tests you go through you get some marks for that they might pass they may fail then there's a part of the grade dedicated to do you comment your code are you using appropriate variable names there'll be a little chunk of marks for that and then they'll be part marks for the implementation how close is it be to being correct so there'll be often part marks for this so usually this is something about maybe a third to sometimes up to 50 percent of the grade is how close is it to being correct so for example if you have any issues compiling these are some part marks you can get but like i said usually the goal at this stage is to make sure you have a program that compiles and executes uh so ah so if we if we know our program runs on replica but the ta marked it on visual studio code so would you consider running it again on replit so this is something that i will talk to the grader about uh because i do think that it depends on which tier i have i know some of them use replic directly other ones will use visual studio code um so keep in mind that i will i will be actually communicating to the graders that if there is any like translation issue uh that will try to be considerate of this fact uh but uh one thing i have to warn you about is that if it's something that is actually like yeah no this happened because there's a core part of your class missing then there's not much i could do about that uh that that is something more of like that that there's something missing and part of your code so just the one example i gave like if you don't actually give initial values for your instance variables typically it's not supposed to compile properly in fact it may even allow you to compile but it will run but visual studio code will have often default values they will set that may not necessarily be zero but replica will usually use zero so just be mindful of this fact but yes i will be communicating to the graders just to make sure like if we have any weird kind of slip-ups in between i will try to be considerate of this fact i do appreciate you bringing that up but yeah if it's something that's more class-based like as a key specification is missing that causes it not to compile then that's an issue but keep on it is g plus plus regardless uh but i must stress that if it runs differently it might that was more of a call between okay is the class being implemented properly as in like is an instance variable being declared properly and being uh actually being initialized properly or is it just that something key or is it just simply some technical matter that is just happenstance happenstance that falls clearly into the category that the greater should reconsider uh yeah we'll be very careful with this uh during the term i do appreciate you bringing that up uh anyways are there any other questions about that but yeah so you'll find that there's a part of it dedicated to compiling and running through some tests then there's gonna be a part of it dedicated to the to like your coding documentation and then on top of that there'll be a part dedicated just to your implementation itself so every assignment i will tell you exactly how many marks each thing is worth so you have a very clear idea what to expect now wonderful wonderful i do appreciate these questions they're very important so anyways uh but yeah there there is no midterm in this in this uh in this offering of this course it'll just be a final exam if you do run into it by any incidents of something saying a midterm in this course online let me know i'll happily fix the typo i do think i got rid of it everywhere uh but yeah now just take a look at this carefully one thing i will mention uh this is usually a policy i do use is that i don't accept late assignments there is no late assignment policy in this course but but because this is a remotely delivered course i need to be wary of the fact that oh yeah everybody uses all sorts of different places somewhere on campus somewhere elsewhere so one thing i do normally is i keep the submission window open until at least 8 30 in the morning of the following morning sometimes i keep it open a little longer i'll usually announce this to you if that were the case but normally i'll i keep it where the deadline usually is at mid just before midnight of that day but i usually leave the submission open until 8 30 more because nobody's going to look at your assignment at 2 30 in the morning right i just think it's not reasonable then at the same time it also helps just in case if there's any weird technical blips you could still submit your assignment you will not be penalized if that happens however after that 8 30 mark i won't accept any assignments unless there's an arrangement that we had prior to the deadline so i must stress that that you need to reach out to me before the deadline if there's any need for an accommodation or some arrangement keep in mind that that's usually on my side to just a discretion uh so usually as i said reach out to me before the deadline if anything comes up okay i'm usually quite happy if there's something like if there's something serious that's happened i'm usually quite happy to accommodate for things but keep in mind that it just saying oh oh i got busy that's not really a valid excuse uh the expectation is that you can complete the work within the scheduled time timeline because the due date is a task in this whole thing but yeah another thing i want to point out is that that for your submission uh so when you get your marks back the policy will be that you need to reach out to the grader within two weeks of you getting your grade back so this the only exception to this will be towards the end of the course where i'll outline a clear deadline to reach out to us but here's the simple policy so because the grader is the one that is assigning your grades and i give them usually a marking guide to help them uh usually reach out to you the idea will be to reach out to the grader first and then if say you have see there is say your co your concern wasn't addressed then you can contact me and let me know about like what happened you could tell me oh yeah the grader said i didn't didn't i couldn't get this mark because of x y and z can you take a look at it i'm very happy to look at things like this but yeah go to the teaching assistant first or greater first then come to me that'll be just the normal chain of command when it comes to like getting any concerns with the assignments resolved when it comes to specifically grading um like i said losing your work is not an excuse for not submitting work uh uh make sure you back up your files if you need to i already mentioned about proctoring software just before class started uh so proctor track will be used for all tests or examinations so the for the final exam proctor track will be used so i recommend you take read this message from the university um this will be the scheduled time of the exam i'll expect that you're available at this specific time normally what i do is i give three hours and 10 minutes just in case because sometimes some students want to attach files and things like that um i do like to make sure that there's some matter for accessibility incorporated but it says three hours here but i may bump it up to three hours ten minutes but you can use that time however you see fit but this is the scheduled time for the final exam it'll be worth 60 percent of your final grade uh big thing that i need to touch upon is academic integrity uh so just remember remember the big a very big part of this course this isn't a group project course this isn't a team course this is a course that is individual effort only so so it's okay to talk to classmates about your assignments it's okay to say discuss things about the assignment but it's not okay to work together on the assignments nor is it okay to copy each other's work or help other students by copying their work uh these are all variant forms depending on how severely severe it is is uh different forms of academic dishonesty whether it be plagiarism or just simply just straight up just this it breaches the expectations of the assignments the assignments are meant to be individual effort so one tip i can give you is when you're talking about the assignments say for example whether it be on campus or remotely is i recommend talk about the assignments if you have questions about the assignments just keep it high level don't go into the nitty-gritty of it just keep it high level uh but also when you have a conversation about the assignment i recommend that you just don't leave anything written down so for example if you have you're doing a conversation on a whiteboard for example i recommend that nobody leaves the conversation with anything written down off the whiteboard and then just erase the whiteboard and leave the conversation that's one way and one tip that i got years back that i found some people found very useful for conversations about things like the assignment and whatnot so you're happy you're happy to chat about the assignment just obviously don't work together on the assignment it's an individual effort so do keep in mind that i take academic integrity or academic honesty very seriously in this class i must stress that for example for the programming parts of the course i usually use software to assist me in trying to find out if there's any form of plagiarism that might be occurring but if there's any suspicion what will happen is i'll i may have to report it so keep in mind that if i see any kind of any kind of leaning that i might see that there's my maybe some forms aren't getting very excited here i shouldn't be getting excited because this is something that i consider rather serious is if if there's any form of academic dishonesty that i suspect i will typically report it um and i usually have some form of evidence for it so keep in mind that it doesn't necessarily mean you did anything i it has to just get investigated so one thing i need to point out about academic honesty and i usually this is the spiel i usually give students is remember it's an individual effort so if you choose to for example look up answers online or seek even assistance online or you say work together as like a team of your classmates now you can always chat with each other but working together is not the same thing as that now if if you do things like this you're taking away an opportunity from yourself to really gain a mastery of the material in this course so in that sense you're almost cheating yourself so the thing is the goal with the assignments is to assess your understanding but also gives you exercises to reinforce things that you see in class so if you don't choose to do that you're losing out an opportunity for yourself to grow and explore these ideas and that at the end of the day that only hurts you at the end of the day so that's why i recommend you just don't do it it's it's it's usually not a wise idea hopefully i'm clear about this are there any questions about that so like there's nothing wrong with chatting with your classmates about anything but just just don't don't get overly specific with things unless it's something very specific you want to just chat about one like one thing but don't usually leave the conversation with a lot of stuff keep it high level if necessary because the last thing you want to do is inadvertently help somebody do something that you like say for example you worked on your assignment and then somebody's out having really a hard time with the assignment don't give them your code i know i've seen incidences of this and it's very unfortunate where a student will actually like help a student and the thing is by helping the students you're almost you're helping them cheat in that sense but i hope that's crystal clear to everybody if you want to get more details about this uh there's some more details here in the academic calendar that you can check out uh but yeah i know as that being said uh tutors uh sometimes i i used to be a tutor years back i did that for a number of years tutors they're meant to help students understand material they're not meant to do your work for you uh don't don't don't ask if you have a tutor don't ask them to do your homework for you okay uh it's not cool some tutors don't understand this boundary uh likewise uh i recommend you don't uh so so i one thing i need to mention here is that uh like i mentioned don't request online help from people to finish your work for you uh that is also a form of academic dishonesty if i find out about it i will pursue it to the fullest extent so i just need to mention that because it's one of those small little things here now if say you have a disability or you want to seek an accommodation i'm very happy to accommodate for these types of things so if you need to seek out this i'm usually very cooperative with these kinds of things because in a course like this it's really important that the course is accessible to everybody so one thing i want to mention is that this lecture is being recorded um but i must stress that it's not that i'm recording everything so for example all the conversations in the chat that's not getting recorded the only stuff that's getting recorded is what's on my screen the stuff that you're seeing right now and my voice that's it uh so i must stress that uh these videos won't contain confidential information from you nor any images or audio from you because i respect your privacy in that regard that also mentions like you know how we mentioned procter track i'm not the biggest fan of it because of the privacy issues that somebody might have with that but it's just a more of a necessary evil of sorts when we're dealing with course delivery online but most certainly the recording policy i respect that specifically because i think it's important in the classroom that you have an opportunity to ask questions if you're not sure about something you should be able to ask questions without any concern of it ever being something that somebody else could see i think that's really important um likewise don't post the lecture videos after somewhere else that that violates my intellectual property uh so always ask for permission if you need to get anything from the lectures otherwise in case unless it's like fair use that's something else but yeah no other than that that's everything i have to say about the course outline are there any questions uh yeah big tips make sure you check the course website regularly um sometimes if i'm not stressed that if you find yourself wanting more examples for example we're covering something like oh like big o notation and you're like oh well dan i look at the notes and i see all these examples can you give like give like another example i'm usually very happy to prepare these things so just reach out to me i'm usually quite happy to make more examples um likewise remember start your assignments as early as you can if for example we're not quite far enough to finish the entire assignment i usually recommend you do it in bits and pieces so whether it be setting up on a little calendar where you're like i'm gonna work on this problem this day this one next day a lot of students i find they have a lot of success doing that other students i know that do the brute force thing that's cool too just keep in mind that those deadlines do exist and i don't accept late assignments uh likewise other than that i think that's everything i have to say about the course outline are there any last questions or anything about the course outline before we hop into things but yeah if you have any questions after class or anything i'm very happy to answer those things so how many days you should give for the assignment so uh if you take a look in this table here that i have on the previous page let me just let me just move up here i would use my page up but i will uh be careful here so i usually like to make sure i'm clear with everybody when it comes to expectations so you'll see that i give the date that i'll roughly assign it and a rough due date here so you'll see that each of these are spaced out about two weeks so if anything wiggles around with this always appeal to the assignment itself uh for example sometimes we take a little longer to cover one thing uh so sometimes i might pad it over so that the deadline moves a little bit like a day or two later so this is just a rough tentative schedule for it but you'll see that to answer your questions two weeks yes it'll be about two weeks that you'll be given for the assignments that's a wonderful question so anytime anytime so yeah if there's any other questions don't hesitate to reach out to me i want to make sure that you come out of this class learning all sorts of fun stuff but at the same time it's also i would consider it rather important stuff too uh but at the same time i want to make sure that you come out of this class and that you get some experience playing around with some of these ideas because some of these ideas will be helpful whether you uh in the future say for example for a course like cs340 and some other courses you're going to see a lot of the things that we're going to have here are going to translate very naturally yes hello hello so anyways let's move on over back to the board if there's anything else i i haven't thought about here uh just let me know i'm usually happy to clarify anything so let's head back over here uh let's get started just give me one moment just gonna turn off just one small thing over on my end okay let me just get the chat don't wanna lose don't wanna lose our lovely chat okay wonderful so anyways let's get started um a question ah take one two two one two two um so i i can answer that question after lecture um so yes so keep in mind uh one thing i'll mention is uh so it was question about lecture video so i will be posting these lecture videos publicly so after what will happen is i'll actually literally walk over to that computer after lecture and i'll start uploading it and then will happen is that you can access it on the course website or or you can for example access a playlist directly either on that youtube channel so if you want to say for example later on reviewing your stuff if you find yourself on youtube for example you could just straight up just go on there and you can watch them if you need um but most certainly uh you'll find that it's best to be participating in class because it gets the engagement going up and if you have any questions specifically it's very helpful but yeah if you find yourself in a position where you're missing class i encourage you if say say somebody get meet up talk to a classmate about taking notes for you sometimes it's pretty helpful but yeah like i said i will be posting my lecture notes after class each time so yeah that's another question so i don't require you to attend lecture there's a lot of different ways that you can learn in this course so you can attend lecture you can watch the videos you can read the lecture notes but i must stress that the best way to do it is to attend class and if there's anything specific i want to point you to in the lecture notes i'll do that but yeah attending class is probably the best way to go but but like i said uh i don't require you to be here in lecture but you'll find that most students when it comes to success in a class usually usually they come to class not anytime anytime but yeah it's because i want to make sure that things are accessible in this course but at the same time if there's anything that comes up while you're doing your studies that there's an opportunity if you need to say if there's something that comes up you can't come to class it will be still available to you most certainly now i do appreciate the questions okay so why don't we get started let's get started so let me just get one other thing here quickly my apologies let's get let's get started so i thought today i'll just do a little bit of an overview of one concept with you but i'm hoping that everything will sort of come together in the coming lectures you're going to find i'm going to lay out a lot of different concepts as we explore things together so so a major a major aspect a major aspect of computer science is the study it's a study study and solving the study and solving solving of computational problems so that's going to be you're going to find that this is going to be a big theme in this course is you're going to find that a lot of the stuff we're going to do is we're going to explore how we can solve different problems i'm going to start laying out a lot of those bits and pieces so that when we get along to study more different kinds of problems or more data structures which you can almost view like a problem in the way that we're going to cast in the next coming lectures in fact let's put an s on this you're going to find that it's going to be quite natural to think about in that way so you're going to find that we're going to transition away from thinking about problem solving as a programming aspect kind of thing and think of it more as i have a computational problem how do i solve that problem and it's not necessarily tethered to just c plus plus instead it will be okay how do i solve the problem and you're going to see that i'm going to try to bridge this gap as we kind of explore through this course so so to design many so to design a solution a solution to many problems to many problems there are often two parts there are often often two parts so this is hence why the course is going to be called data structures and algorithms is that we're going to see that there's a data structures part and an algorithms part so the first one is how to organize data how to organize that data so this is the part that's the data structures part so this is just simply a systematic way so a systematic way of organizing of organizing of organizing and accessing accessing or modifying or modifying data that's the first part of this it's how we're going to organize the data so we're going to see a lot of different ways we can organize data based on how we would like to actually encode that information which one natural mechanism we're going to see is this idea of an abstract data type which will be one of the main mechanisms for us to talk about the idea of a data structure so the second part is obviously how to solve a problem the other big how how to solve how to solve a problem so this is the algorithms part of the course so you've probably seen some algorithms already up to this point for example you may have seen for example some basic sorting algorithms so this is just simply a step-by-step procedure step-by-step procedure for performing so for performing some task for performing some task in finite time so i'll be laying some more concepts on top of these i'm just trying to give us a big picture look of things so we have data structures and we have algorithms so first i'm going to talk about data structures and then we'll focus more on about algorithms so let's head on over here let's let's go this way let's go this way so let's talk a little bit about data structure so i must stress that the con the term data structure is a broad and a broad term it can mean a lot of different things to a lot of different people the broad term it's not even just that it's also a subfield of computer science so people just study data structures but most certainly we need some working definition for us in this course so to build on this we need to start talking about some things that you've seen before which i think is very natural the first thing is a concept called a data type now i'm sure that you've seen the idea of a data type before right can somebody tell me a data type that you've seen for example something like in c plus so can somebody tell me a type like say like a primitive type for example yeah like an ant like integers yeah integers are a type string yes string is strings of type floats floating point numbers most certainly these are wonderful examples um so you can think of these all as types right so that's what i'm going to refer to as a data type it's a broad term very broad category of things you're going to see that my definition also naturally captures this so these are things that we've seen before right we're boo you're very good very good so so a data type a data type is a collection a collection a collection of values or objects like i said it's really vague um you can get quite detailed with the idea of what a type is but that's not this course this course we're just trying to introduce a lot of these ideas and bring them together so so one thing i must stress i'm going to put a comma on this you're going to see that i'm going to make this even broader than maybe we may have thought about before and of course like cs115 that can be that can be mathematically specified there's this m word this is sometimes i colloquially call this the m word i i often will call it mayonnaise mustard i know that some students when as soon as they see this word that they're like oh no dad what are you doing um i assure you we're gonna see a lot of mayonnaise in this course but most certainly it's going to make a great sandwich um so does the minute you see this don't worry it's not anything to be intimidated by it's actually quite natural so let's let's chat about this so that can be mathematically specified if i'm very reluctantly using this word very often because i want to be i know that some students they see that word they're just they're just like ah now some students are very enthusiastic about it which is great but i don't want to exclude anybody so can be mathematically specified or given concretely given concretely concretely in a programming language so you may have more experience with the latter than the former but guess what we know all sorts of different kinds of objects for example that can be mathematically specified such things like integers uh those are mathematically specified objects like that's an example likewise i could take any one of the types that we talked about in programming like a c plus plus i can also specify the mathematically speaking as well right you can think of it just as an abstract representation of that so now this is where things are going to kind of shift so we have some familiarity with this idea of a data type so oftentimes we would like we would like a mathematical there's that m word again with mathematical abstraction and there's that word again abstraction you know how uh there's this other concept called abstraction you may have seen a little bit of it before but you're gonna find that it's a very powerful mechanism that you may have seen a little bit towards when you start talking about types say for specifically class types the idea of polymorphism and things like that you talked about this idea that you can have different tides of objects right most certainly there's another notion this idea of called abstraction where what you have is say for example i have a car like have a car now i could use a car but i don't necessarily have to know all the inner workings of the car right as long as i know how to operate the car but you know that at some point to push the pedal of the car requires me to do much more than just pushing a pedal to cause the car to go forward right so we're working at a higher level of abstraction versus a lower level one where for example if i'm operating a car i don't have to worry about all the inner workings of the car but the thing is is i would like to know and ensure that the car operates as i would expect it to right so you're going to find that this idea is a very natural one as well when we start talking about data structures we would like to have data structures that operate as we expect them to but i need some model to describe how i would translate say i have this model of a thing that's based on a data type i would like to have some way of implementing it that's what i would like to be able to do but to do that i need some idea of a model for the thing to implement it if you get what i mean so we're gonna see that this idea is gonna be quite natural for us this idea that there's different granularities of abstraction where you have less specific or high level specific to launch lower level specific this is a common idea say for example in computer science for example some programming languages are operate at a much lower level versus those operate at a higher level for example there's a much bigger difference for the control you have over a computer system at assembly versus what as say say java or python but anyways i i'm just trying to ease you into this idea that we're gonna see a lot of in this class so the first time you see it it's okay if you don't get it at perfectly yet we'll see a lot of it you'll get exposed to it quite often so abstract model of a data type of a data type plus operations it supports plus operations it supports so this is so notice that now i'm going to have it where there's a data type but it also has a set of operations so it has these operations it supports and i want to have some way of describing this to you now if i had a concrete representation of this this would be a natural way of talking about the idea of a data structure right so for example when you have say like uh you can even think of a string just like a data structure right because you think it has a collection of characters right uh so you have operations that you could do on the string so that's something very natural to think of as a data structure right but how do i describe to you what a string should do that is kind of one of those things that i would like to be able to accomplish without having to tell you how it actually works just like my car example where if i use the car i don't necessarily need to know all the inner workings of the car i just need to know that the car works right so the car has all sorts of things that it does i can push on a pedal but the thing is the pedal i don't need to know what the pedal does i just trust that the car works right so you're going to find that this is quite a natural translation to this idea that we're going to talk about called an abstract data type this is referred to this is referred to as an abstract data type so i'm going to give you a definition and then we'll do an example so we're going to talk about what this concept of an abstract data type is now at first when you see the definition it should remind you a lot of this one i have here for the for our uh for our data type but you're going to see it's going to have this idea of a set of operations too so let me write it here and then we'll do an example so so so we're gonna have an abstract data type and the idea at least the hope will be that if i have this type it will specify a set of operations and it tells me the specifications of sort and for those that are interested in where this course sort of sits in the pantheon of software development so for some some students they're very interested just computer science some students are interested software development or both this course will sit somewhere between high level specifications say a user gives you versus the straight up implementation and programming language so this is what the notion of abstraction in this context will be that i could give you one of these abstract data types and what will happen is i would like to be able to implement it but i just want to know what the type is so that's what the notion of this abstract data type is hence why it's called and that's abstract as you're gonna see in a moment so a collection so this is the definition we're gonna use a collection of values or objects so this should remind you of the data type definition right a collection of values or objects and a set of operations and a set of operations on those on those values or objects now this is the part that usually students look at me and like dan what the heck does that mean uh i'll explain in a moment that is accept that is accessed accessed only so my stress is only through through what is called an interface so i must stress that the interface is what defines the operations and that's what an abstract data type is so you might ask dan so that part reminds me of the data type definition right um but there's this part about the set of operations and it says it's accessed only through an interface you might say dan what what the what is an interface now you may have heard of this concept before possibly in different programming languages actually an explicit way you can build these for example programming languages like java for example will have an explicit feature that that actually mimics this abstract idea of an interface so you got to think of the interface as this broader concept it's not just a feature in a programming language so you know how i talked about the car for example a car can have a sequence of operations that can happen right so for example i could push on the pedal the pedal causes it assuming that i am not in park and i assumed i am going straight right it will allow me to drive forwards right now i can specify a sequence of operations i can do with the car just keeping things high level at the moment so naturally i could define that operation i could push on the gas pedal i could push on the brake i could toggle the radio i could turn it on and off these are all operations now i don't know how the car actually does it right now the interface what the interface is is the description of all these features so for example pressing the gas pedal having the brake pedal and toggling the radio these are all features of the car right but the thing is if imagine i gave you a giant list of all the things a car can do at terms of operations this would the idea is that the interface has a list of all these operations and they define what the abstract data type is so we're going to see this in our example here shortly but the idea is that the interface hides away how exactly this thing actually does everything instead the idea is that the interface will just keep and define the what it is not how it does things so think of it as it provides you the what but not the how and what the how will be is that each one of these operations can be something that you could specify in a programming language or in a high level description as an algorithm so before we proceed are there any questions because i'm going to do an example showing you this idea of this abstract data type and i might i will make a couple quick remarks in a moment about how this would be something you can translate into c plus plus so if you really just want to have this idea of an abstract data type like in the most purest sense and a lot of people they might do it that way some won't but most certainly this might remind you of something actually in c plus plus so there's a feature that in c plus that i can give you a whole list of the operations like you think it was as the functions and i don't have to tell you how exactly they're bought what their bodies are i can just tell you what the signatures of the of the functions are there's a very natural mechanism for example in c plus lights that's capable of doing this does anybody know what that is it starts with a c so for example i can have this idea of yeah class so for example i can have a header file where i could specify the name of the class and i could give you all of all of its attributes and also all of its operations right but i don't have to put them all in my header file right the header file gives me the specifications of those functions so a class is a nice natural way of defining this idea of an interface in c plus because it's encapsulated in one singular form as opposed to just a whole bunch of functions just kind of just sitting off to the side right like you can have a header file that has a bunch of functions in it right but the thing is a class encapsulates and hides away those details so so are there any questions i see a hand up i see a hand up yeah no no that's a wonderful question this is a very common one so if you're asking questions like that you're right on the right track so uh we'll see this in the example actually i'll include an example of some c plus code showing you what you could actually translate this into like in c plus if you really wanted to go purist with this a lot of people don't necessarily but i encourage you to think about it uh but uh they answer your question about okay so like where exactly is i i if i could clarify the issue is where like where exactly is the line between the abstract data type and an actual implementation is that really kind of the heart of your question okay wonderful so i think my aunt my answer will be that the example's gonna specify more what i mean by this so we'll see is the example and then this will clarify hopefully your question so you'll find that just like my example with the car that i talked about i don't necessarily know how the car goes forward right okay maybe if i studied enough engineering i most certainly could uh but most certainly i don't know like you got to imagine almost like it's like a user using your your type they don't necessarily know how it works inside of it just like for example when you use a string in c plus plus we don't necessarily know what's happening underneath the hood of the c plus plus code right we just know that a string i could do all these fun operations with a string right but notice i could use the operations but the thing is here i'm not necessarily requiring that it's actually implemented i'm just saying that it has this set of operations that are accessible through this interface this interface is the boundary line between an actual implementation and what it is so think of this as the what when you actually try to implement it that's the how so let's actually see the example and you'll see exactly what i mean it's a wonderful wonderful question so let's do the example here i'll i'll give you we'll talk about the example here a little bit so one thing i want to mention is that in c plus the notion of an interface isn't exactly defined but it is like a sort of work a worker i don't know if workaround is the greatest term most certainly you can specify this abstract idea of an interface in c plus plus the way you do this is using something called an abstract class so an abstract class is simply a class where every one of the functions is what we call purely or pure virtual so in the notes i will include an example of how you can actually define this so all it is is just a class where you have all of your signatures and each one of them you you don't have implement the bodies of them instead you put equal zero afterward uh you'll see the example in the notes so i'll post that after class uh so if you find yourself curious about like okay so some some students i know will really like and appreciate the idea of actually taking and picking up and implementing it um other students will be like okay it's just an idea so here we go so here's an example that i really like showing students and we'll see this idea again i thought it would be a good idea to introduce it to you so to elaborate on the concept of an adt consider a stack so so we're going to consider what is called a stack so you might ask dan what is a stack so here's the thing a stack is an abstract data type now you may have heard of the concept of a stack before possibly but the idea is that a stack is actually just a collection of objects but it follows a certain set of rules and the natural thing i'm actually building is to think of it just like a stack of plates so with a stack of plates i could put for example something on the top of the stack i can also remove something from the top of the stack so notice that there's two operations i've sort of described to you right the idea of putting an object on the stack and one that is to remove from the top of the stack and like maybe retrieve it these are two operations for example in a stack we'd often refer to the putting an object on the top of the stack we'll call that the push operation and to remove an object from the top of the stack is a pop operation so the idea is that i'm going to define the adt in terms of its operations but i'm not going to tell you how i do this like how i did this process just now i'm not going to tell you how it's done i'm just going to tell you what it is so so the big thing with the stack so let me just first define what a stack is so a stack a stack is a collection a collection of objects that follow what this is the rule that it's often referred to as last in first out which people refer to as lifo very often lifo rules and what i describe to you here when i have my stack of plates i'll show you an example what i mean by this lifo idea in a moment lifo rules for insertion and removal and removal so you can imagine like a stack of plates so you might ask okay so what does that mean what does that mean so what is this last in first out business so see if i have my stack of plates now suppose i didn't have a stack of plates yet i get my first object i push i'm gonna put it on the top of my stack now the idea in a stack is that i don't have access to the bottom of of the sack i only have access to the top of the stack and that's where i'll do insertions and removals so notice that the order i do this in when i bring in my next plate i put on the top of the stack so notice that this is the most recent object i just placed on the top of the stack so if i remove my next object to the top of the stack what's this this is the most recent object i put on the stack right that's what i mean by last in first out is it the last thing you put on comes out first so you can imagine i have to define a couple of these operations wow how i put insert objects into my collection how i remove them out so this is how i'm going to define the stack to you and you're going to notice very quickly that oh yeah it doesn't really matter that what like i don't need to know what the implementation is this is what a stack is so a stack a stack is an abstract data type that supports the following the following operations so i must stress that you also have other operations you can also define just the point is to call it a stack in the context we're talking about i need at least these two operations we'll have a much much more kind of fleshed out definition of a stack later on in the course so here's one operation called push and it takes notice that every time i define one of these operations i give you its name i'm going to tell you what its parameters are and i'll tell you in my description how if i need to return anything so i said it's a specification of a what so let's push it's supposed to add it adds an element e to the top of the stack to the top of the stack so when i did that insertion every time i put on the top stack that's a push operation so notice that i didn't tell you how i'm going to do this right i this is what just what push is it's a what it's what it is another operation the other one that we've seen is this one called pop so what is pop i'm just going to remove so it removes and returns the top element element from the stack so if it's ever empty where i don't have any plates we'll just make it so it returns null here or null if the stack is empty meaning it has no objects so keep in mind you can define other operations for example for a stack other ones include things like peak we'll talk more about these operations later on in the course size this tells you how many objects are in the stack and is empty tells you if the stack's empty or not so notice the way i described them to you i told you what the operations are did you see anywhere that i described to you like how i do the operations nowhere right i just tell you what you're supposed to do these are what these are what's these are specifications so with that being said what i'm going to do next time is i'm going to show you how i can implement a stack so what we're what we're going to see is that our working definition of a data structure which like i said it's a broad a data structure is a broadly used term an abstract data type some people call that a data structure some people call the implementation of the abstract data type a data structure i usually consider both data structures but usually it's more appropriate for me to talk about the data structure is something we actually can implement so when we come back i'll talk more about how these push and pop operations can work and we'll see a couple ways we can represent it actually we'll see at least one we'll see at least one we'll see how much time we have uh but i'll ask you to take a look in the notes to see if you if you're curious about how i could take this idea of an interface and write it up uh what is e it's an element and so it's just some object so notice that i can make this e an integer i can make it i can make it literally a plate object like i could define a plate object it could be i could define the type that goes into the stack if i like but notice that here i'm just telling you what it is that's a wonderful question so for example in c plus if you ever use something you'll see it in the labs called a template you can actually specify a stack like you can actually implement like a stack but you could give it specifications but you don't have to specify its type you could actually have it just like a placeholder that you can actually dictate the type if you need it at that given time it's actually kind of neat but with that being said let's stop right here when i come back i'll show you how we're going to represent the stack i'll give you a working definition for a data structure and then what we'll do is from there we'll see where we're going to take us for talking about algorithms and problem solving so we're going to see we're going to see a lot of different concepts laid out here so again i'll ask you to take a look at the part that's called interfaces in c plus i'll include a little bit further in the notes so if you want to get a little ahead and want to read a little bit about oh how we're going to represent this stack um i want you to just take a quick peek at this thing called this little section it's in a box it'll be towards the end of the notes in the lecture notes at this point keep in mind i'll update the lecture notes as we go along look for this small section just take a quick peek at it i just want to give you some familiarity of what this might look like if you were to write out an interface in c plus and so what what for example something like a stack would look like so that being said i want to say thank you very much and i'll see you tomorrow have yourself beautiful day i'll see you later