I see. Hi. I'm so sorry I'm late. I for some reason thought it was in uk time and I'm in France. Ha, so sorry about that. Do you have 15 minutes at the end of the class to make up for. I need to check. Yes, I do have time. Okay? If you have time, then we can do that. If you don't have time, we can always reschedule for I'll just give an extra 15 minutes or 30 minutes next class that way, that way to make up for the lost time. Otherwise it's not fair to you. Okay, let's get started. Let's do some theory as usual. Is there anything that you want to cover in theory that you're not comfortable with already? Or do you just want to keep doing the thing that we were doing before where we're just growing over, we can just keep going. Okay, let's have a look. Syllabus. Gcsc your past gcsc. Okay. Do you know what a database is? Yeah, what is it in your own? A not necessarily server but just to store data, say. Yeah, it's a place to store data. But tell me everything that you know. Is there anything you know anything else you know about a database? Stores it stores large amounts of it effectively. Yep, large amounts. But anything more specific, how does it store data? Well, there's. There's columns and tables. What's it called? A group of data that's represented not represented, but. Accessed with a primary key. Absolutely. Do you need a primary key in a database? You don't, but it's good to have one for faster access. Yes. What does it remind you of? A primary key? A hash. Yeah, exactly. My primary key equals hash. So it needs to be a hashable type, like a string or just a number. If I have say I want to store a database of student names, grades, subjects and. Phone, would you mind drawing me a table of a database? Let me give you access. There you go. Would you mind just drame a table on here to show what it would look like? Oh, my bad, I think I moved down in your mouse, went with me always. Student ID, great. Unfortunately. Exactly. So technically here, so you added student ID, which is good, but what else could you use as a primary key if there was no student ID? Zoname Yeah, probably write their name. And you could probably, let's say, for example, there was no student ID, but you had surname and name. Could you make a primary key from this? Yeah, it's unlikely to have two see same names exactly. You can take a primary key here of surname and name, a joint primary key. So joint pk, so basically you would say something like joint primary key, surname name, and then these two columns would form a primary key together. So you would need these two to reference anything. But is there something else that you could use here instead of surname and name? If you don't have student ID. First, den ID, sorry, just a normal ID, you could, but I'm thinking more in terms of the phone, right? Everyone's gonna to have a different phone number here. So if you weren't able for any reason to have a student ID, which you should have anyway, you could use the phone. It's much more accurate than just the name, right? And obviously, thinking more abstractly, what could be the issue with taking phone as the primary key? If you if you just take phone as primary key. They may they may not have a phone, but let's assume that everybody has a phone. That's a good point, though. That's a really good point. They may have one or more. I think in terms of like a school, like practically where might we find a scenario? Say this is in say this is not in University, but like in your grade, right? Maybe in grade twelve. I don't know if you use grades or some other method to rank where you are, but let's say you're in grade twelve, which in French is second year, and I don't know I don't know what it would be in where you do school, but let's say you're in a particular grade at school and you're not a University or anything. So the phone number is probably not your phone number, right? So what does that change? No, think about siblings. They may have matching phone numbers because exactly, you may have matching phone numbers if you have a sibling that has that's your user. Parents are using the same phone number, then suddenly you've got a collision because they're both using the phone number. Maybe your parents hate you. They named you and your sibling the same name. I hope that's not the case with you, but maybe they did. And so now you've got a name and a phone which are the same and your primary Key No longer applies, right? So these are things to think about when you have a primary key. When you have a primary key, you need it to be unique. The best way to do it is student ID. Now let's so what would you use for student ID? Let's say you had to make a key for student ID. What should the key be? Right? Let's say you've got a program called make new students versus a function, right? And it adds a student to the records. What should you take into account when you're creating a student ID? How would you make a student ID? A global variable that increments each time a student comes in very good. So youhave something like counts, right? And it starts at zero. And every time you make a new student boom, count plus one. Right. And then whatever is the order, you just add it to this list. That's actually a perfect way to do it for students. What about this though? What if it's a user ID password? Maybe card number. What about now? The user ID Oh, sorry, Yeah you're you're trying to figure out a way to do user ID, can you still use discount method here? Probably you can, but what's what's the problem with using account method here? What's what could be a possible issue down the line? I mean, I don't see any issue. Think about nefarious people, mean people, right? People who might hack your database. The reason why I work, sorry, they might paid lots of accounts. They they could, but I'm thinking more if they steal your data. Notice here we don't have any information on the user name or the actual user. I know it's a bit of a straction. This is a quick question, but you don't have any revealing information, except of course the card number. But you do have some information about the user, you basically knowing what order they signed up, because you know the first user is going to be zero, the second one is going to be one, two, three, four, five. So if you want to hack data for a certain user, you just need to figure out when did they sign up, which is actually a lot easier than you might think, because usually there's logs, there's ways to find out where the user actually first created an account. And so that's why a user ID being just incremental is not really the safest option. What you really want to do is you want to create a hash from some of the attributes here. So youtake a hash of a password, hash the card number, the phone, maybe the name, right? Maybe some kind of, Yeah, you just hash all of that and then maybe youalso take a random number. Brand plus hash and then you just output user ID and youmake. Sure. It's unique in the whole system and then that would be your user ID. And the chances of her collision are extremely, extremely low. Cool. What if I were to ask you what a relation is? What's the relation in the database? How we table, how an element at the table, or how a table relates to another element in another table. Could you give me an example by drawing a set of boards? Able. So the purchases. And. Of. And then one element here. Relate to menu. Exactly what does this signify here? This little thing that you made here? One relates to many, yes, because one customer could relate to multiple purchases, right? What should I do it with the dothat like? Because I think well, the way that you did it seemed correct to me. Both seem correct to me. To be honest, I would not have given you any negative points for not using a dotted line for me. It's quite clear if you use this that it's one to many and then this is many to many. Rebut. I guess it doesn't matter. I guess it would understand regardless. But you wouldn't have the other way around, right? You wouldn't have this because many purchases can't link to many users, right? Like of course they can, but you can't have one purchase link to two users. Doesn't make any sense. I think you figured that out. Okay, very nice. And the what's the advantage of doing this? Why don't we just put them all in the same table? Don't get messy. After a while, your table gets absolutely huge. Not only that, but it also becomes really slow to access. I'm not going to go into database access tooling like logic, but it's quite complex and it's not. And basically, that's why we do all of these things, right? That's why we have so many tables. And we try to relate everything in different ways because man, working with database, like difficult databases, are tough. As a side note, if ever you go into industry, doing too many subtables is also bad. It makes accessing very, very, very slow because you have to go through every single table and just kind of make sure that it all fits together. If you want to have to read something, you have to access a bunch of tables and it's quite slow. Yeah. Okay. So I'm going to ask you a following set of questions. So let's see how a student. Student subjects. Subjects and then let's say. Let's say so student ID subjects and then name so zero 12 math, science. English. Math. And then Econ geo. Name Bob built. Check. Okay, what nominal form is this in? Do you know what nominal form is? No. So basically, nominal form is a way of organizing A A table. What stands out about this table? What what to you is almost wrong about this table? These subjects contain surof. Many strings. Yeah all right. You've got math, you've got science. They're all in the, you know, they're all in the same thing. This makes no sense. There's a comma. So how would you restructure this table? No need to draw it like I did with all the lines or everything, but maybe just give me an example of, let's say, Bob or bill. How would you restructure this table to make more sense or even restructure the rows? You don't even have to change the columns. But how you how would you change this? Minimal changes would be to put the strings in order at least. Yeah, that's a very good point. In order of what would you put in an order? I mean, if you're going put maths first and then science, then you should also put maths first and then English. I have a counterpoint. What about sorting them alphabetically? This is alphabetical. This is alphabetically. What do you think about that? Yeah, that also works. I prefer your point, though. I prefer your point. It does make more sense to put math, but like at the same time, if that makes sense, right? I prefer so I go into total change, then I would list every subject and make it another row and make them boolean variables. Okay? I see kind of like A A cabinary number almost on what they're doing. So you might have math, science, right, English. Geo, right. So then youhave something like one, one, zero, zero, one, I think that's so one, zero, zero and then one and Econ, I forgot icon one and zero, zero. That could work. What what would this be useful for this kind of format here, where maybe you have every single math, science thing and you got student ID here? What would that be useful for? And by that I mean, like, is it easier to write, to read? What would be the main purpose of this kind of formatting? Access? And also to write to, sorry, to access and write to, it would be very quick to access, right? Yoube able to quickly go in, change it from one to zero very quick, and then go out just, you can modify it quickly, but you can also read it very quickly. Matscience English geboom, where might this become a problem in the future when you have tons of subjects? Yes, exactly. You end up with a table with like hundreds of columns, which could be a problem later on. Now, of course, actually, for a, for a small high school, you know, this kind of would make sense. This kind of formats, just a boolean variable for what people are taking, makes it easy to visualize. But usually, if you have this kind of thing in a high school, you then want na extend it. We want to extend it with timetables, which geography, class, science, English, etc. So then this quickly becomes redundant. But this is a good layout for the problem that we've posed. Another solution is to turn this. This is called zero nominal form. Now that's a scary name. So what does this actually mean? Let me delete here. Have you heard of nominal form before? Let me search what nominal form actually definition is. Okay, basically nominal form is the normative form. So basically it's it's I think it was made by this guy when he was first creating databases, forgot his name, who created nominal one db. Edgar F code d Yeah. So basically Edgar F cod, he came up with this normalization technique. You have zero and F1 and f. One nf nf stands for nominal form. Two nf, three nf. And actually the guy was bored enough to make ten of them. But we're not going to go through all ten today. We're going to just go through these three, which you need to know. So what what do these mean? So right now, zero nf is kind of a match. We've got student subjects names. We've got commas in there. We've got at least we've got a student ID. So that's good. But you you know sometimes you don't. What zero nf is is just a mess. It's just data that's not formatted properly. One nf means that items are atomic. Do you know what atomic means? Do you know what atomic means? No, basically think of it as an atom. It's singular. And what do you think that means in this context? Only one value should be in each, exactly, only one value per paraof. So this is in zero and f if you want to go from zero nf. To one nf. Then every single value should be atomic. So how how do we change from this to be from atomic to from non atomic to atomic? Very simply, just close row some ideas out there and then we can maybe quickly write them down. The most simple thing you can do is just to relist these things. So student ID zero, they do math. And name is Bob, but student ID d zero also does English science. Yeah you see a problem, right? What else? Student ID one bill, he does English. Right? That's bill, but he also does math. Etc., what's the obvious glaring problem here? It gets quite large after a while, it gets quite large. But there's another problem here as well. No, you have to access at least twice to get every data. Yeah we have to access twice to get at least every data. And we have repeating we have repeating student ids here. Like of course, I guess it's not the biggest problem in the world. But ideally, if we query for a student ID, we want to get one item. We don't want really a student ID to have multiple, especially for a table with every Yeah exact quid. So that's kind of where two nf would come in. And this is kind of where youstart doing normalizations. So then youstart saying, okay, student ID zero is Bob. Because basically the issue here is, look. These are different, right? This is fine. Zero math, zero science. Makes sense. 290, zero does math. 290, zero does science. That's fine. But look at this. We've got Bob in there. Like why is Bob in there? We're storing Bob twice. We're basically repeating data. We're wasting space. So we split this up. We have one table with zero Bob, one bill, and then you have a second table linked to another table. Exactly. You've got math zero, whatever he was doing science. And now this makes a ton more sense, right? Because now you're not restoring bill every single time. You're only storing what you need to store. You're only storing bobband bill once here. You don't have a whole new column where you would have, you know, a string is quite heavy because usually a string will have a maximum of 256 characters in a database. Times uncode de a string, so 16 bits. So it's quite a lot of data that's that's being saved. And this is called second nominal form where you split out the things that need to be split out. And this kind of mixes in with third nominal form. The gap between the two are very small, but let me get the exact difference for you. 32. There's three nths. Yeah there's also you know another thing here is that right now we've only done it via the primary key, right? The primary key kind of defines everything. But you might not have to have a primary key. Let's say, for example, we have student. Name. And then we have something like country and then city, like the country they're from and the city they're from, right? Let's say you've got a lot of students that are from London, right? Button. You can just create something, a table name button. Exactly. Yes, you've got it. Why do we need this? We can store only one of these. We only need to know the city so we can know the country so that stop storing the country every single time. And instead, if we need to know the country, let's have a country where let's have a City Country table. Where we just have London, uk, Paris, France, right? And then basically that would make it a lot easier. Yeah, I think if you've got it, and this is this is not even a primary key. This is just a relational key which can be used. I mean, it's primary to this table, but you kind of get what I mean. Okay, let's move on to licode if you want. Do you want to move on to licode? Yeah okay let's Yeah生。Okay, there you. Go. You had it open and ready. Let's go let's sort them by easy. I almost want to give you a medium question, but but let's just do one more easy. Yeah, scroll down a bit. Keep going because there's a few here that are just sql. Keep going. Stop. Let's see here. Go to count complete tree nodes number 222. How do you do it? Nosing Python though? You doing it? Python? No, no, I'm just gonna see, okay, it just has the value and not yet. Is it similar in Python two? You could also do in Java percplus, you won't see anything good to say. According to Wikipedia. Just. Is it just the same thing as we like the reverse binary tree we did last time? Yeah, it's very, very similar. It's very, very similar. In fact, if if you feel too comfortable with this question, maybe we can do another one if you prefer. Yeah I'm just thinking about getting a stack if it has another branch storage and then go on and then increment by one. Yeah, I think you've got this. Okay. Then maybe, maybe, maybe you're good on this question. We can go back. Let's have a look at some more. Let's see. Let's go for maybe power of two to three, one. Oh, that's easy. Without or recursion, that's a little harder. This is a brain teaser, it tea bit of your logic. Bulean yeso if the number is a power of two, return, if it's not, then return. Are you sure it's that? What does that give you? Is that a power of two or is that something else? I'm going to try. One is. Oh. Are sure no. All right. Aha. You're close, though. You've got the right idea. You can do this in one line. I think it's a brain. It's a brain teaser. But don't spend too, too long. I can give you some hints. Give me some hints. Yes. What do all okay, let me phrase it in a way that won't give it away. If you have a power of two, right. How do you know it's a power of two? Firstly. Visible by two divivisible way two, what else does it have? Think about, for example, two to the power of eight, right? Yeah, it's 256. If you were to represent that number, 256 in a different way than just 256, what might you find? Or to the power of seven. No, 40, the power of four, four to power four. Yeah, you could find four to power four, but let's say you had to represent it using a different number system. So binary operations, how would 250 about drashifting? That's that's not a bad idea. You're on the right track. But what does 256, 128, 64, 32, what do they all have in common? In a different representation than just numerical. 24, eight, 16 bits. How do you write 32 in binary? One zero zero time is zero right there. Zero os and how many how would you write 256 in binary? Bit of a trick eight zero 18 zero seven I think it's maybe seven zero zero one but you're there right, seven zero zero a one what about two? Yeah. One zero and no what about one? Oh, so there's only going to be 11 and the whole thing exactly. If you put into binary representation, there's going to be only 11. If there's more than 11 in the binary representation, it's not a power of two. But it says not to use a loop, so how would I gluthrough reach? Having. If you, if you take the binary number, would I sort of loop through each digit in the binary? Are you sure you need a to loop? Think about, okay, let me, let me get my pen out. Let's say you have the number eight, right? And binary one zero zero zero. We want to check without going through all of these numbers, is it A A, what it called a power of two? Power of two? Yes. So for exercise, I want to find a way to do something like this. I want to say, okay, I want a one and just a bunch of zeros. How can I figure it out? How can I figure out if it's a one and just a bunch of zeros using only bit operations? Well, if I have a zero here and three ones, I or this, I'm gonna to get one, one, one, one right? One, one, one, one. And if I end this with one, one, one, one, then I should get all should be one. Let's take a different number six. If I have six then I have zero 11 zero. There's a formula to come up with this number. If I use the same exact formula, I don't want to reveal it to you because otherwise it be too easy. But if I use the same exact formula, I do an or and then an. End right, then I should get false. Right. So is that formula just flipping each bahow? Would you how would you guess from eight to this number here? What's this number? Seven? Yes, exactly. So what you want to do is you want to do n or n minus one Yeah and how do you get this number here? New and the result. You can Yeah p you can just add. And. And. Or I don't know how it works in c plus. Plus I know how it works in pplus. Okay, I'll let you think about that. Do you need me to I'll keep this up if you want want do you want me to remove it? Do you want me to keep it up? Hello. So could do you keep it up please? Sure. Yeah first. And for this one here that we end, make sure, because for Python it is this, but I don't know, for C++, for C++, there's another method you can use which might make more sense. But you'll just have to think of a way to get from this number to this number, one, one, one, to try and find a way to create that, what we call a mask. All this. Yeah, I have a feeling false. I have a feeling okay. You're going to have to come up with a different number than one for this one. You're going to have to come up with another way to get to to this number here. Mmm. I would think more of for example, here, the binary binary number eight has four bits. So if it has four bits. Then to get to this number. To get to this number, it's going to be two to the power of five minus one. Right, because you have four so it's going to be the amount ts of bits here. So the number of bits in n two to power 52, power of n plus one, n sorry, count of n plus one and then minus one to get the four ones here a bit confused basically. So imagine here. So that's not an easy question to be honest, especially since most people cheat because I think the loop actually works. But here. You have four bits. So if you were to take two to the power five, you would definitely have one, zero, zero, zero zero, but one, zero, zero, zero minus one becomes. 11, one, one, which is the number you need here. And so just to give a bit more context, when you use these operators in C++and in Python, the way that these are calculated is it says, okay, this or that, this or that, this or that, this or that. Okay, that that makes sense. And then here for and and then Yeah, same thing there. So this basically is just a little trick where you say, okay, if I have the number eight, I need to turn it into some kind of binary representation where I can count the numbers. For example, a string, once I've got my string, I count the length of the string. If the length of the string is, say, four, then you know that there's four bits in my number n. If there's four bits in my number n, then I've got two, then two to the five minus one will give me all ones because imagine for here, two to the five would be 16. 16 minus one is 15, and 15 is just one, one, one, one, right? You've got eight plus four plus two plus one, which sets ts up to 15. And so that will get Shinto max work. Then I'm not sure what int max does. I feel like int max would be because int mabut, I'm worried that if you have, and this is why I'm not sure about C++, I'm worried that what int max is doing is put it's adding a bunch of zeros over here and then it's ending it. That's what I'm worried about. No, it's a definine in the c standard and the C++standard library. It's. Okay, maybe I misunderstood my limitations in sea R showing. To the 31 minus one, this is the value. But I'm worried that if you say, for example, but I'm not sure about C++functionality. So maybe this is a question, for example, ChatGPT. But what I'm worried about is that let's say you do 88 and inmax. And I'm most worried that you have a, it just adds a bunch of zeros. So instead of it being like, so it wouldn't be eight, it would be like one, one, one, one, but then it would add a bunch of zeros to fit to the inmax, if that makes sense, like before it, and then that would result to it. It's already an end. So that's why I chose intermax. If it's unsigned and then it be uintermax. I see. Okay. I think I'm really sorry. I think I don't have the C++expertise to properly solve this question in C++because in Python, it would make sense to me. Let me read about C++because I think I think you're on through the right track. So I think it's just A C plus issue that I'm just not eligible about. Let me let me check it out and that what's the name of the problem or power f two? With. Power. Yeah, let me check. Okay, okay, for C++there's actually a smart way to do this. So in Python I would have used my method, but my method is is it doesn't work in C++but it's very very similar. So I think you can solve it by yourself because you're very smart. So I'm just gonna to give you three or four minutes to think about do the exact same thing, right? An and and ine or so, you're using an and and an or but instead of using once you're using zeros. So try to figure it out using using zeros and see what it gets you. Using zeros Yeah using zeros. So instead of instead of going okay, I'll help you out because this is this is a bit tricky but here we're doing an or right Yeah instead of doing an instead of doing an or let's do an end. What does that give you with an end? All zeros. Yes all zeros and then I not that yes exactly. And then you noit. So not n and n minus one. Yep, very good. Did you submit or did you Press run? Okay. Yes, very nice. Wait. Oh, no, Henry. There's one more exception. There's if you go back to the description over here. There's also negative numbers. So you need to add a check here. You need to add a check. And basically say is for example, is minus two a power of two? Than v sorry, it's not it's not minus two. Any negative number is not a power of two. Ready study s case, of course n equals negative. Oh it works fine and watch Oh because it brings it up to three smart so you need something for zero then. It can file optimizes this. Not understanding the if n you can do Yeah this is pretty good and just make sure that it's above zero or equal to zero. Or if n is if n is zero. First false, if n is zero, it's just false. Yeah. Because no no power of two power of zero equals one. So no power of two can never be zero. Yeah two power minus one is just equal to one root two, one over root two. And I'm gonna to see if there's an alcome. How do you see your test in C++? I'll be completely honest with you. I think every time we've tried it hasn't worked, but I think you're you're there. I think this is just should be if n equals equals zero return return false instead of Yeah so then this returns false also. So then must be built to zero. Yeah, I think this is pretty good. Zero overflow because okay, this is why you might need if n is below zero gen just return zero because a signed integer might have a might just tabecause if you do assigned integer minus two whatever like max inminus and then you minus one, then you have an overflow. So you might just need to say if n is below zero. Yes, there we go. I don't know how those guys did it. They did it with the wild Yeah cheaters, hackers. This this is a very complicated brain teaser. By the way. You should you should be quite happy you figured this out. A lot of people really just don't. So you've got a good understanding for bits and boperations with this with this problem. Henry, I'm really sorry I was leave today. I Yeah, I hope I made up for it with these 15 minutes. Look, if your parents are are because I mean, it's their money, so I'm happy to do an extra ten minutes next class as well to kind of make up for it. Of course, only if you want to on next next Sunday. And if that works, then we can do an extra ten minutes next next session to make up for it. Maybe we can even do two leads. Thank you. Apart from this, I mean, good work. Once again. You're really getting good at these. I think these are quite useful because they really try to, they practice your your your logic solving skills, not just your programming skills. I know it's it's a bit slow at first. We're doing only easy questions youdefinitely be able to do some medium questions, but it's definitely a time thing. Just to give you an idea for me, a medium question takes ten to 15 minutes. So if we were to do a medium question, it would take us the whole hour. And I'm not sure how much youget out of it. So I think it's better to kind of do some easy questions together, maybe in your own time. If you feel like doing a medium, you can go for it. Try, but try an easy one. You can tell if a medium is easy by the acceptance rate. So for example, if you see letter combinations of phone number, Yeah that one, that one's actually that one's actually very difficult. This one is doesn't seem like it should be, but it is it is quite difficult. But if you see a medium with like 75% acceptance rates, you know and you've got some time on your hands, you can go for it. I think you're more than capable. But be ready to like spend two or three hours Banang your head against the table asking why it's not working. Like generates parentheses, right? Number 22, I think yoube able to do that. That one. Yeah, it's it's not an easy question. It's not an easy question. You might have to look up some YouTube tutorials, but but if you figure it out, you're going to learn a lot about programming. But you know if you're frustrated and you're spending more than like if you're spending more than 30 minutes or more than an hour on this and you're really not make any progress, I would first suggest if you scroll down, you've got usually you've got hints, you don't have hints, but I would look at the topics and maybe the discussion. Yeah and then people, you know, they help you out to the discussion, maybe to watch a YouTube video about it. It can help you a lot. Yeah, thank you. But have a great weekend and I'm sorry again, please apologize on my behalf to your parents, and I hope to see you next week. Yeah, bye, bye, bye.