ULUSHAHIVE

Recently I gave a brief interview to WeProject. I think people who are just starting their career may find it useful 😺

Let's continue from the above post. Share the weirdest setups you've ever had in the comments section. Ko’ramiz qanchali qiziq narsalar chiqarkin 😺 Rasmdagi mening eng noodatiy setupim. Casesiz PC, yana ham eski ko’rsatadigan monitor, ajoyib layoutli keyboard va … Shu paytgacha o’zimda unique deb bilgan narsam sichqonchani chap qo’lda ishlatish bo’lgan. Shunaqa qiladigan qizni ko’rsam yaxshi ko’rib qolsam kerak 😵

Bugun o’zbekligimga bordim… Yaxshi ma’noda 😺 Uyda ham, ofisda ham o’tirib yoki yotib ishlar edim. Tabiiyki charchadim. Turib ishlagim keldi, lekin, standing deskim yo’q. Keyin o’zbekligim tutib butunlay boshqa narsaga mo’ljallangan narsadan o’zimga mos use case yasadim. Kim topa oladi to’liq setup qanaqa ekanini? 🥤

Bugun Khurshid Juraevning uyiga kelsam, bir kandidatni Optifly’ga CatGPT projectga interview qilish kerak ekan. Jarayondan lavhalar 😵

#algo Randomized Algorithms (Part 3) - Monte-Carlo Avvalgi postlarda randomized algorithms to’g’risida umumiy tushuncha va Las-Vegasga misol ko’rgan edik. Bu postda Monte-Carloni bir masala yechimida ko’ramiz. Qanday muammoni yechadi: Deterministic algoritmlarga solishtirganda Monte-Carlo usuli odatda straightforward’roq bo’ladi. Shuningdek, xatolik ehtimoli bor bo’lgani bilan, qabul qilish mumkin bo’lgan xatolik va resurslar o’rtasidagi trade-off to’liqligicha o’zimizning qo’limizda. Problem: Random qiymatlardan foydalangan holda PI ning taxminiy qiymatini hisoblang. Yechim: Tasavvur qiling, tomonlari 2 ga teng bo’lgan kvadrat bor va unga radiusi 1 ga teng bo’lgan aylana ichki chizilgan. Quyidagi qadamlarni N marta (number of samples) bajaramiz: 1. random orqali (x, y) nuqta generate qilamiz. 0 ≤ x, y ≤ 1. 2. Agar x^2 + y^2 ≤ 1 bo’lsa inside counterimizni birga oshiramiz. Yuqoridagi qadamlarni N marta bajarib bo’lgach, 4 * inside / N ni dasturimiz hisoblagan PI ning qiymati sifatida qabul qilamiz. Nega -1 ≤ x, y ≤ 1 emas? Chunki bizga chizgan shaklimizni to’rtdan bir qismi uchun yechimni to’rtga ko’paytirish kifoya, chunki hammasi teng kuchli. Bu orqali kamroq sample ishlatib yaxshiroq accuracy’ga erishamiz. NOTE: Albatta PI ning qiymatini hisoblashning ko’pgina boshqa yo’llari bor, lekin ushbu usulda biz aynan randomized algorithm orqali ham shu muammoni yechish mumkinligini ko’rdik. Bu usulning ustunligi, boshqacha ko’rinishdagi versiyalarga ham modifikatsiya qilish orqali ishlatish mumkin. Learn Algorithms With ULUGBEK

Благодарность! Ахату Рахматовичу Азаматову, моему наставнику и учителю в области математики, я хочу выразить огромную благодарность. Его влияние на меня просто неоценимо. Он не только поддержал мою страсть к информатике, но и зажег во мне пламя жажды знаний, которое горит в моей душе до сих пор. Без его поддержки и мудрого руководства я бы не стал тем профессионалом, кем я являюсь сегодня. Моё образование и развитие как специалиста в значительной степени определились его неутомимым участием в моей жизни. Улугбеку Абдиманабову, моему нынешнему тренеру, я хотел бы выразить глубокую признательность за его беспрекословную поддержку и руководство на протяжении нашего совместного пути. Под его руководством мы поставили перед собой амбициозную цель участие в финальных этапах ACM ICPC. Благодаря его неизменному труду и мудрым советам мы продолжаем двигаться к этой цели с неуклонным упорством и решимостью. Личный канал Улугбека Абдиманабова: https://t.me/ULUGBEK_ABDIMANABOV

Well, what can I say? Reading such messages gives a good feeling 😊

#algo Randomized Algorithms (Part 2) Randomized algoritmlar worst-case scenarioni yaxshilash uchun ishlatilishini aytib o’tgandim. Ikkita video resursni ko’rishni maslahat beraman. Birinchisi shunchaki qiziq va foydali, ikkinchisi esa turli xil coding problemlarni random yordamidagi yechimlari. ➡️ Las-Vegas, Randomized Quick Sort: Qanday muammoni yechadi: Hammaga ma’lumki, klassik quicksortning worst-case scenariosi O(N^2) saralashga tenglashtirib qo’yadi. Bu holat, saralanayotgan elementlar qisman yoki deyarli saralangan holatda yuz beradi. Yechim: Pivot elementni tanlash jarayonini random orqali tanlash kifoya. Bu algoritmning worst-case holatidagi vaqt asimptotikasini O(N^2) dan kamaytirmaydi, lekin shunday holat yuzaga kelish ehtimolini deyarli 0 ga yaqinlashtiradi. Klassik holatda atay shunday testcaselar tuzish mumkin bo’lsa, random versiyasida bunday holatni yasashning iloji deyarli yo’q.

Function RandomizedPartition(A, low, high) pivotIndex = Random from low to high …

NOTE: Bu worst-case holatda ham average asimptotika bilan ishlashni ta’minlash uchun bir yechim. Dasturlash tillaridagi sort funksiyalari bunday holatlarni turli xil usulda handle qiladi. Masalan C++ va Java dasturlash tilidagi sort funksiyalari hybrid saralash (bir necha usulni birga ishlatish) orqali o’rtacha tezlik va worst-case performance o’rtasidagi balansni ta’minlaydi. Shuningdek quicksortning klassik usulidan boshqacharoq dual-pivot versiyasi ham bor, o’qib ko’ring. Keyingi postda Monte-Carloga misol ko’ramiz 😉 Learn Algorithms With ULUGBEK

Agar kimdir faqat kod yozishni biladi deb o’ylagan bo’lsa… 🫠

#algo Randomized Algorithms Bu postda radnomized algorithms to'g'risida umumiy ma'lumot beraman. Qachon ishlatiladi va nima uchun kerak, shuningdek, qanday turlari borligini bilib olasiz. Keyingi postda esa haqiqiy algoritmlarda misol ko'ramiz. Randomized algoritmlar zamonaviy kompleks muammolarga o’ziga xos yechim berishi bilan yaxshi tanish. Bunday algoritmlar o’z jarayonida hech bo’lmaganda bir marta random sonlarga asoslanib biror vazifani bajaradi va bu orqali yechimni ajoyib, taxmin qilib bo’lmas va worst-case scenarioda deterministic algoritmlardan ko’ra ancha tez ishlaydigan qilib beradi. ➡️Turlari Las Vegas: Tassavur qiling, juda katta stavkali kazino o’yinlaridan biridasiz va sizga aniqlik juda muhim. Siz algoritmdan xatolik ehtimoli nol bo’lishini hoxlaysiz. Ha, to’g’ri taxmin qildingiz, bekorga kazinoni misolda keltirmadim. Chunki bu turdagi randomlashtirilgan algoritmlar o’z kazinolari bilan mashxur bo’lgan shahar nomiga qo’yilgan va Las Vegas algoritmi deyiladi. Aniqlik deganda kerakli natijaga erishishning iloji bo’lmasa “Failure” yoki “Infeasibility” to’g’risida ogohlantirish ham nazarda tutiladi. Bunga eng yaxshi misollar: Randomized Quick Sort, Randomized Binary Search. Monte Carlo: Endi esa tasavvur qiling, sizga qo’yilgan muammoda aniqlik juda qimmatga tushadi (computationally intensive), lekin aniqlik tarafdan kompromisga boriladi. Qisqa qilib aytganda aniqlikni tezlikka trade-off qilib, ba’zida inaccurate natija beradigan algoritmlar Monte Carlo deb ataladi. E’tibor bering, xatolikka ruxsat berilgani bilan, buning ehtimoli yetarlicha kam bo’ladi. Ya’ni deyarli doim aniq natija olamiz, lekin aniqlikka 100% kafolat bermaymiz. Aslida bu nom ham kazinolar bilan bog’liq (qiziqqan o’qib oladi 🥤). Eng taniqli misollar: Karger–Stein algoritmi va Fast Monte-Carlo Test for Primality. Learn Algorithms With ULUGBEK

#algo Union-Find Algorithm Kruskalning bir qismi aynan shu algoritmga bog’liq edi, kelinglar endi shuni ham ko’rib chiqamiz. Qanday muammoni yechadi: Element qaysi to’plamga tegishli ekanini va ikkita to’plamni tez birlashtirish imkoniyatini beradi. Qaysi to’plamga tegishli ekanini esa graphda sikl paydo bo’lish bo’lmasligini tekshirishda ishlatish mumkin. Problem: Kruskalda berilgan masalani eslang. Yechimni bir qismida

Har bir qo’shilayotgan edge grafda cycle yaratib qo’ymasligini tekshirishni unutmang! Agarda cycle yaratsa, u edgeni shunchaki skip qilib yuboring, u javobning qismi bo’la olmaydi.

degan edim. Aynan shu qismini DFS yoki BFS orqali tekshirmasdan, optimalroq hal qilish kerak. Yechim: Avvaliga har bir orol o’zi alohida to’plamda deb qaraymiz. Endi A va B orollarni bog’lovchi ko’prikni (yo’lni) javobga qo’shmoqchimiz. Avval ular bir to’plamda yoki yo’qligini tekshiramiz. Buning uchun orol indeksi X orqali u qaysi to’plamga tegishli bo’lsa, shu to’plamning root indeksini (representative node) qaytaruvchi find operatsiyasi bor. Agarda find(A) == find(B), demak A va B orollar bir to’plamga tegishli va (A, B) yo’lni qo’shish sikl paydo bo’lishiga olib keladi. Agarda har xil to’plamga tegishli bo’lsa ularni union operatsiyasi orqali birlashtiramiz. NOTE: Algoritm tez ishlashini taminlash uchun find operatsiyasida path compressionni ishlatishni unutmang. Buning uchun shunchaki rekursiya orqali X tegishli bo’lgan to’plamning representative node’ini topayotganda quyidagi kabi ish qilsangiz yetarli: `parent[X] = find(parent[X]) Learn Algorithms With ULUGBEK

Bugun Optiflydan birinchi marta bayram sovg’asini oldim 🤗 3 yoshli jiyanim shokoladga buncha hursand bo’lmasa kerak 🙈 Ko’proq shokolad berishar deb ko’proq ishlayman endi 😺

#travel Yet another trip has come to an end. I have a private channel where I’ve been leaving notes for myself for several years. The best advice I've given myself, which has proven true time and again, is this:

Try everything. If you can't afford the experience or don't have the right circumstances, work towards them, but never ever give up hope. Try as many things as possible!

Enjoy 🙃 Planning to make posts on some randomized algorithms too 🫶

#algo Kruskal’s algorithm Qanday muammoni yechadi: Kruskal algoritmi weighted graphda barcha nodelarni mumkin bo'lgan minimal umumiy og'irlik (narx) bilan samarali bog'lash muammosini hal qiladi. Shuning uchun u Minimum Spanning Tree (MST) ni topishda qo’llaniladi. Ma’lumot uchun MST bu - initial graphdagi barcha edgelarni shunaqangi subsetiki, bu subsetdagi edgelar barcha nodelarni bo’g’laydi va hech qanday sikl paydo qilmaydi. Shuningdek, klassik holatda umumiy edgelarning weightini ham minimallashtirishga harakat qiladi. Problem: N ta orol bor va u orollar orasiga M ta most qurish variantingiz bor. Har bir orol orasidagi masofa ham berilgan. Qurilish narxini kamaytirish uchun sizga umumiy uzunlik qiziq. Shunaqangi qurish kerak bo’lgan mostlarni tanlab olingki ularning umumiy uzunligi minimum bo’lsin va istalgan oroldan boshqasiga yo’l bo’lsin. Yechim: Barcha orollar, ular orasidagi qurilish mumkin bo’lgan mostlar va ularning masofalarini qulay graf ko’rinishida saqlab olamiz. Mostlarni (edgelarni) masofalari bo’yicha o’sish tartibida saralab olamiz. Bir boshidan edgelarni javob to’plamga qo’shib boramiz. Har bir qo’shilayotgan edge grafda cycle yaratib qo’ymasligini tekshirishni unutmang! Agarda cycle yaratsa, u edgeni shunchaki skip qilib yuboring, u javobning qismi bo’la olmaydi. Hamma nodelar connected bo’lmaguncha, boshqacha qilib aytganda N-1 ta edge topmaguncha qo’shishda davom eting. Agar garantiya berilmagan bo’lsa, algoritm boshida feasibility checkni ham tekshiring. Edgelarni tanlash usulidan tushunish mumkin-ki bu Greedy Algorithm hisoblanadi. Note: Edge qo’shayotganda cycle yaratib qo’ymasligini Union-Find Algorithm orqali tekshirishingiz mumkin. Learn Algorithms With ULUGBEK

#algo A* (A-star) algorithm Qanday muammoni yechadi: A* o’zining ikkita nuqta orasidagi eng qisqa yo’lni Dijkstra’s algorithm ga solishtirganda effektivroq va tezroq topib berishi bilan ajralib turadi. Tezroq ishlashiga asosiy sababi bir nuqtaga kelish tan narxi (masofasi or whatever) va destination pointga yetib borishning taxminiy narxlarini to’g’ri combine qilib qaror qilishidadir. Aynan shu taxmin qilishi heuristic deb yuritiladi. Tezliklarini solishtirish uchun ushbu videoga refer qiling. Problem: NxM grid berilgan. Agar (i, j) katakda ‘.’ bo’lsa bu katak bo’sh, ‘#’ esa bu katak band deganini bildiradi. (start_x, start_y) katakdan (end_x, end_y) katakka borishning eng qisqa yo’lini topish kerak. Yechim: A* ning yechimi Dijkstra amakinikidan uncha farq qilmaydi. Ochiq va yopiq set bor. Ochiq set bu - yurish uchun kandidat kataklarimiz va ularga yurish costlari. Yopiq set esa biz kirib bo’lgan va qayta process qilishni hoxlamaydigan kataklar. Dijkstrada qo’shni kataklarga yurishni shunchaki yurish masofasi yoki narxlarini yig’indisi orqali ifodalasak, A* da heuristic functionimiz qanday implement qilinganiga qarab bu logika istalganicha bo’lishi mumkin. Lekin, klassik holatda quyidagi ko’rinishda bo’ladi: shu katakkacha kelish narxi + destinationgacha yetib borish taxminiy narxi. Shuning uchun tepada takidlaganimdek, A* da ko’p narsa heuristics qanday yozilganiga bog’liq. Misol uchun, ushbu holatda heuristic functionni manhattan distance deb qarashingiz mumkin. Note: Ba’zi hollarda average run timeni yaxshilash uchun bir necha xil hueristic function yozib, current state qandayligiga qarab mos keladiganini ishlatish ham o’rinli bo’ladi. Learn Algorithms With ULUGBEK

Vietnam trip o’z nihoyasiga yetdi. Ketgim kelmayapti 🫠 Captions for pictures: 1. Sevishgan daraxtlar 2. Dam olaymi yoki ishlaymi 🤔 3. Anavi bola nima qilyapti? 4. Raiden 5. Aya, men uchyapman 6. Kitoblarimga yana bir background 7. Three steps above heaven in a reverse universe 8. Men 9. Bulutlar mendan pastda (yohud men ulardan balandda 😁) 10. Osondagi qo’llar